数据结构与算法(二)分治算法(Java)

目录

    • 一、简介
      • 1.1 背景
      • 1.2 定义
      • 1.3 步骤
      • 1.4 时间复杂度
    • 二、经典示例
      • 2.1 二分搜索
      • 2.2 快速排序
      • 2.3 归并排序(逆序数)
      • 2.4 最大子序列和

一、简介

1.1 背景

在学习分治算法之前,我们先来举一个例子。

假如你有一个存钱罐,过年家人给的钱都会放到存钱罐中。当我们想要清点存钱罐中的钱时,一堆钱混乱的放在一起很难清点,并且容易算错。那我们可以这样,先将存钱罐中的钱分成几小份,然后再求和就可以了

在这里插入图片描述

如果我们还是觉得各个部分的钱数太大,依然可以进行划分然后合并,比如每凑够100元为一组等。梳理下思路,我们之所以这么做是因为以下两点:

  1. 划分后的子问题更易求解;
  2. 父问题的结果可以直接由子问题的结果计算得到。

其实这就是一种分治的思想。

1.2 定义

分治算法:是一种 将一个问题分解为多个子问题,分别求解这些子问题 的解决方法,主要用于递归计算中

1.3 步骤

具体来说,分治算法通常包括三个步骤:

  1. 分解原问题为若干子问题;
  2. 解决这些子问题,递归地运用分治算法;
  3. 合并这些子问题的解为一个整体。

1.4 时间复杂度

分治算法的时间复杂度通常为 O(nlogn)


二、经典示例

分治算法的经典使用示例包括:

  • 二分搜索
  • 快速排序
  • 归并排序
  • 最大子序列和
  • 其他:最近点对、大整数乘法、Strassen矩阵乘法、棋盘覆盖、线性时间选择、循环赛日程表、汉诺塔等。

2.1 二分搜索

二分查找

二分搜索是分治算法的一个示例,只不过二分搜索有着自己的特殊性:

  • 序列有序;
  • 结果为一个值。

思路:

  • 先将一个完整的区间分成两个区间;
  • 两个区间本应单独找值然后确认结果,但是通过有序的区间可以直接确定结果所在区间,然后对结果所在区间进行再次划分;
  • 直到找到值。

代码实现:

实现方式有递归和非递归两种,但是非递归用得更多一些:

/**
 * 二分查找
 * @param nums 数组
 * @param target 目标值
 * @return 位置
 */
public int binarySearch(int[] nums, int target) {
    // 超出范围
    if (target < nums[0] || target > nums[nums.length - 1]) {
        return -1;
    }
    // 判断边界
    if (target == nums[0]) {
        return 0;
    }
    if (target == nums[nums.length - 1]) {
        return nums.length - 1;
    }
    // 二分查找
    int left = 0, right = nums.length - 1;
    int index = 1;
    while (left < right - 1) {
        System.out.println("查找次数:" + index++);
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (target < nums[mid]) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return -1;
}

2.2 快速排序

快速排序,简称 快排,也是分治算法的一个示例。

思路:

  • 快排每一次遍历会选定一个数,将比这个数小得放左面,比这个数大的放右面;
  • 然后递归分治求解两个子区间;
  • 快排在划分时就做了很多工作,当划分到最底层的时候,最后的序列值就是排序完的值。

快排是一种分而治之的体现。

在这里插入图片描述

代码实现:

public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}
/**
 * 快速排序
 * @param nums  数组
 * @param left  起始位置
 * @param right 结束位置
 */
private void quickSort(int[] nums, int left, int right) {
    if (left > right) {
        return;
    }
    int l = left;
    int r = right;
    // 中心轴
    int pivot = nums[l];
    while (l < r) {
        // 找到第一个小于k的值
        while (nums[r] >= pivot && r > l) {
            r--;
        }
        nums[l] = nums[r];
        // 找到第一个大于k的值
        while (nums[l] <= pivot && l < r) {
            l++;
        }
        nums[r] = nums[l];
    }
    nums[l] = pivot;
    quickSort(nums, left, r - 1);
    quickSort(nums, l + 1, right);
}

2.3 归并排序(逆序数)

排序数组

快速排序在划分的时候做了很多工作,而归并排序则恰恰相反。

思想:

  • 先按照数量均匀划分为两块区域;
  • 两块区域再各自进行划分,直到每块区域长度为1;
  • 合并的时候再两两进行有序的合并。两个有序序列的合并仅需 O(n) 级别的时间复杂度即可完成。

而逆序数再归并排序基础上变形同样也是分治思想求解。

在这里插入图片描述

代码实现:

public int[] sortArray(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
    return nums;
}

/**
 * 归并排序
 * @param nums  数组
 * @param left  起始位置
 * @param right 结束位置
 */
private void mergeSort(int[] nums, int left, int right) {
    int mid = (left + right) / 2;
    if (left < right) {
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

/**
 * 两两排序
 * @param nums  数组
 * @param left  起始位置
 * @param mid   中间位置
 * @param right 结束位置
 */
private void merge(int[] nums, int left, int mid, int right) {
    int[] arr = new int[right - left + 1];
    int l = left;
    int r = mid + 1;
    int index = 0;
    while (l <= mid && r <= right) {
        if (nums[l] <= nums[r]) {
            arr[index++] = nums[l++];
        } else {
            arr[index++] = nums[r++];
        }
    }
    while (l <= mid) {
        arr[index++] = nums[l++];
    }
    while (r <= right) {
        arr[index++] = nums[r++];
    }
    System.arraycopy(arr, 0, nums, left, arr.length);
}

2.4 最大子序列和

最大子数组和

题目:

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

思路:

最大子序列和问题,我们可以使用 动态规划 的解法,也可以使用 分治算法 来解决问题。最大子序列和 在合并的时候并不是简单的合并,因为 子序列和 涉及到一个长度的问题,所以 正确结果不一定全在 最左侧 或 最右侧,可能出现结果的区域为:

  • 完全在中间的左侧
  • 完全在中间的右侧
  • 包含中间左右两个节点的一个序列

在这里插入图片描述

代码实现:

public int maxSubArray(int[] nums) {
    return maxSub(nums, 0, nums.length - 1);
}

private int maxSub(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    int mid = (left + right) / 2;
    // 计算完全在mid左边的最大值
    int maxSubLeft = maxSub(nums, left, mid);
    // 计算完全在mid右边的最大值
    int maxSubRight = maxSub(nums, mid + 1, right);

    // 计算包含mid的最大值
    int tmpMaxLeft = nums[mid];
    int tmpLeftSum = 0;
    for (int i = mid; i >= left; i--) {
        tmpLeftSum += nums[i];
        tmpMaxLeft = Math.max(tmpMaxLeft, tmpLeftSum);
    }
    int tmpMaxRight = nums[mid + 1];
    int tmpRightSum = 0;
    for (int i = mid + 1; i <= right; i++) {
        tmpRightSum += nums[i];
        tmpMaxRight = Math.max(tmpMaxRight, tmpRightSum);
    }
    int maxSubCenter = tmpMaxLeft + tmpMaxRight;

    if (maxSubCenter >= maxSubLeft && maxSubCenter >= maxSubRight) {
        return maxSubCenter;
    } else {
        return Math.max(maxSubLeft, maxSubRight);
    }
}

整理完毕,完结撒花~ 🌻





参考地址:

1.「五大常用算法」一文搞懂分治算法,https://zhuanlan.zhihu.com/p/328368839

2.十大经典排序算法及动图演示,https://zhuanlan.zhihu.com/p/449501682

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/228966.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【AI】以大厂PaaS为例,看人工智能技术方案服务能力的方向(2/2)

目录 三、解决方案 3.1 人脸身份验证 3.2 图像审核&#xff08;暴恐、色情等&#xff09; 3.3 人脸会场签到 3.4 机器人视觉 3.5 视频审核 3.6 电商图文详情生成 3.7 智能客服 接上回&#xff1a; 【AI】以大厂PaaS为例&#xff0c;看人工智能技术方案服务能力的方向&…

【vuex】

vuex 1 理解vuex1.1 vuex是什么1.2 什么时候使用vuex1.3 vuex工作原理图1.4 搭建vuex环境1.5 求和案例1.5.1 vue方式1.5.2 vuex方式 2 vuex核心概念和API2.1 getters配置项2.2 四个map方法的使用2.2.1 mapState方法2.2.2 mapGetters方法2.2.3 mapActions方法2.2.4 mapMutations…

【思路代码详解】2023mathorcup大数据复赛B题妈妈杯高校数学建模挑战赛电商零售商家需求预测及库存优化问题

2023 年 MathorCup 高校数学建模挑战赛——大数据竞赛 赛道 B复赛&#xff1a;电商零售商家需求预测及库存优化问题 问题一 目标&#xff1a;制定补货计划&#xff0c;基于预测销量。 背景&#xff1a;固定库存盘点周期NRT1, 提前期LT3天。 初始条件&#xff1a;所有商品…

temu日本站在哪里入驻

在跨境电商领域中&#xff0c;Temu是拼多多推出的一款备受瞩目的平台。如今&#xff0c;越来越多的商家希望将自己的业务扩展到日本市场&#xff0c;而在Temu日本站上入驻就成为了一个不可忽视的机遇。本文将为您介绍如何在Temu日本站上入驻&#xff0c;并提供一些有用的技巧和…

excel做预测的方法集合

一. LINEST函数 首先&#xff0c;一元线性回归的方程&#xff1a; y a bx 相应的&#xff0c;多元线性回归方程式&#xff1a; y a b1x1 b2x2 … bnxn 这里&#xff1a; y - 因变量即预测值x - 自变量a - 截距b - 斜率 LINEST的可以返回回归方程的 截距(a) 和 斜…

Spring Boot实现接口幂等

Spring Boot实现接口幂等 1、pom依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http:…

记一次xss通杀挖掘历程

前言 前端时间&#xff0c;要开放一个端口&#xff0c;让我进行一次安全检测&#xff0c;发现的一个漏洞。 经过 访问之后发现是类似一个目录索引的端口。(这里上厚码了哈) 错误案例测试 乱输内容asdasffda之后看了一眼Burp的抓包&#xff0c;抓到的内容是可以发现这是一个…

12.08

1.头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QDebug>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);~Widget(); signals:v…

2023五岳杯量子计算挑战赛数学建模思路+模型+代码+论文

赛题思路&#xff1a;12月6日晚开赛后第一时间更新&#xff0c;获取见文末名片 “五岳杯”量子计算挑战赛&#xff0c;是国内专业的量子计算大赛&#xff0c;也是玻色量子首次联合移动云、南方科技大学共同发起的一场“企校联名”的国际竞赛&#xff0c;旨在深度融合“量子计算…

正则表达式(7):转义符

正则表达式&#xff08;7&#xff09;&#xff1a;正则表达式&#xff08;5&#xff09;&#xff1a;转义符 本博文转载自 此处&#xff0c;我们来认识一个常用符号&#xff0c;它就是反斜杠 “\” 反斜杠有什么作用呢&#xff1f;先不着急解释&#xff0c;先来看个小例子。 …

TCP传输层详解(计算机网络复习)

介绍&#xff1a;TCP/IP包含了一系列的协议&#xff0c;也叫TCP/IP协议族&#xff0c;简称TCP/IP。该协议族提供了点对点的连接机制&#xff0c;并将传输数据帧的封装、寻址、传输、路由以及接收方式都予以标准化 TCP/IP的分层模型 在讲TCP/IP协议之前&#xff0c;首先介绍一…

Python列表的排序方法:从基础到高级

更多Python学习内容&#xff1a;ipengtao.com 大家好&#xff0c;我是彭涛&#xff0c;今天为大家分享 Python列表的排序方法&#xff1a;从基础到高级&#xff0c;全文3400字&#xff0c;阅读大约10分钟。 在Python中&#xff0c;列表是一种常用的数据结构&#xff0c;而对列表…

<习题集><LeetCode><链表><61/83/82/86/92>

61. 旋转链表 https://leetcode.cn/problems/rotate-list/ public ListNode rotateRight(ListNode head, int k) {//k等于0&#xff0c;或者head为空&#xff0c;直接返回head&#xff1b;if(k 0 || head null){return head;}//创建last用于记录尾节点&#xff0c;移动last找…

vue 使用 h函数

我的项目前端使用的vben-admin框架。现在有个需求需要在列表中显示一个自定义链接 先贴出做成功的效果如下图。 在做之前通过咨询和搜索得知 可以用vue的h函数来返回一个dom。 那我就去看vue官网对于h函数的说明和示例&#xff0c;大致浏览了一页&#xff0c;感觉还是有点迷糊…

实时动作识别学习笔记

目录 yowo v2 yowof 判断是在干什么,不能获取细节信息 yowo v2 https://github.com/yjh0410/YOWOv2/blob/master/README_CN.md ModelClipmAPFPSweightYOWOv2-Nano1612.640ckptYOWOv2-Tiny

SpringBoot系列之启动成功后执行业务的方法归纳

SpringBoot系列之启动成功后执行业务逻辑。在Springboot项目中经常会遇到需要在项目启动成功后&#xff0c;加一些业务逻辑的&#xff0c;比如缓存的预处理&#xff0c;配置参数的加载等等场景&#xff0c;下面给出一些常有的方法 实验环境 JDK 1.8SpringBoot 2.2.1Maven 3.2…

Gerber文件使用详解

目录 概述 一、Gerber 格式 二、接线图示例 三、顶层丝印 四、顶级阻焊层 五、顶部助焊层 六、顶部&#xff08;或顶部铜&#xff09; 七、钻头 八、电路板概要 九、使用文本和字体进行 Gerber 导出 十、总结 概述 Gerber文件:它们是什么? PCB制造商如何使用它们? …

C# 编程新手必看,一站式学习网站,让你轻松掌握 C# 技能!

介绍&#xff1a;实际上&#xff0c;您可能弄错了&#xff0c;C#并不是一种独立的编程语言&#xff0c;而是一种由微软公司开发的面向对象的、运行于.NET Framework之上的高级程序设计语言。C#看起来与Java十分相似&#xff0c;但两者并不兼容。 C#的设计目标是简单、强大、类型…

智能优化算法应用:基于战争策略算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于战争策略算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于战争策略算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.战争策略算法4.实验参数设定5.算法结果6.参考…

轻松操纵SQL:Druid解析器实践

一、背景 在BI&#xff08;Business Intelligence&#xff09;场景中&#xff0c;用户会频繁使用SQL查询语句&#xff0c;但在平台运作过程中&#xff0c;面临着权限管理、多数据源处理和表校验等多种挑战。 例如&#xff0c;用户可能不清楚自身是否具备对特定表&#xff08;…