leetcode - 分治思想

news/2024/9/22 15:47:36/

分治 - 快排

这里快排我们统一使用 数组分三块 和 随机产生基准值的方法实现排序

数组分三块:

. - 力扣(LeetCode)

整个思想即将数组按照基准值分为三个区间 , 具体实现: 三指针实现.  遍历指针 , 左区间右边界指针 , 右区间左边界指针

class Solution {//三指针法//格外注意边界值问题//[0,left - 1]  值为0//[left,right]  值为1//[right + 1,nums,length - 1] 值为2public void sortColors(int[] nums) {int left = 0;int right = nums.length - 1;int i = 0;while(i <= right) {if(nums[i] == 0) swap(left ++,i ++,nums);else if(nums[i] == 1) i ++;else swap(right --,i,nums);//注意这里右边交换时i不用++,}}private void swap(int left,int right,int[] nums) {int cur = nums[left];nums[left] = nums[right];nums[right] = cur;}
}

过程

为什么要使用随机数?   基于随机数产生基准值而进行快排时,时间复杂度最为接近O(Logn)

class Solution {public int[] sortArray(int[] nums) {sort(0 , nums.length - 1 , nums);return nums;}private void sort(int left , int right , int[] nums){//递归结束条件if(left >= right) return;int random = new Random().nextInt(right - left + 1);int flag = nums[random + left];//确定基准值int leftFlag = left;int rightFlag = right;int cur = left;while(cur <= rightFlag){if(nums[cur] == flag) cur ++;else if(nums[cur] > flag) swap(nums , cur , rightFlag --);else swap(nums , cur++ , leftFlag ++);}//循环结束时,leftModel - 1为左区间最后一个元素 , leftModel + 1为右区间最后一个元素//递归sort(left , leftFlag - 1 ,nums);sort(rightFlag + 1 , right , nums);}private void swap(int[] nums , int l1 , int l2) {int cur = nums[l1];nums[l1] = nums[l2];nums[l2] = cur;}}

快速选择算法:

. - 力扣(LeetCode)    数组中第k个最大元素  , 要求时间复杂度O(n). 

这道题比较容易想到的解法是 借助堆.    但是题目中要求时间复杂度为On , 堆就不满足要求了.

时间复杂度为O(n). 我们就要想到快速选择排算法

原理:  快排数组分三段的基础上不去对每一段进行排序,而是通过三个区间的元素数量判断目标元素在哪一个区间进行分类讨论:

class Solution {//快速选择算法//基于快排数组分三块的思想:分三块后通过分类确定目标范围private static int dest;public int findKthLargest(int[] nums, int k) {Solution s = new Solution();s.quickChoose(0 , nums.length - 1 , nums , k);return dest;}private void quickChoose(int left , int right , int[] nums , int k){if(right <= left) {dest = nums[left];//这里不要忘记赋值return;}int flag = nums[new Random().nextInt(right - left + 1) + left];System.out.println(left+":" + right+":" +flag);int l = left;int r = right;int cur = left;while(cur <=  r){if(nums[cur] == flag) cur ++;else if(nums[cur] > flag) swap(nums , r -- , cur);//注意右边换过来的是一个新值,cur不进行++else if(nums[cur] < flag) swap(nums , l ++ , cur ++);}//分类讨论 , 根据区间内元素的数量确定下一步计划//1: 目标元素在大于基准值的区间if(right - r >= k) quickChoose(r + 1 , right ,nums , k);//2: 目标元素等于基准值,直接进行返回else if(right - l + 1 >= k) {dest = flag;return;}//3:目标元素在小于基准值的区间else quickChoose(left , l - 1, nums , k - (right - l + 1));}private void swap(int[] nums , int num1 , int num2) {int cur = nums[num1];nums[num1] = nums[num2];nums[num2] = cur;}}

. - 力扣(LeetCode)   库存管理: 选出库存最小的cnt个商品

class Solution {private int str;private int end;//使用快速选择排序public int[] inventoryManagement(int[] stock, int cnt) {quickSort(stock , 0 , stock.length - 1 , cnt);int[] dest = new int[cnt];for(int i = 0;i < cnt;i ++) {dest[i] = stock[i];}return dest;}private void quickSort(int[] nums , int left , int right , int cnt) {if(left >= right) return;int l = left;int r = right;int cur =  left;int flag = nums[new Random().nextInt(right - left + 1) + left];while(cur <= r){if(nums[cur] == flag) cur ++;else if(nums[cur] > flag) swap(r -- , cur , nums);else swap(l ++ , cur++ , nums);}//分类讨论if(l - left > cnt) quickSort(nums , left , l - 1 , cnt);else if(r - left + 1 >= cnt) return;else quickSort(nums , r + 1, right , cnt - (r - left + 1));}private void swap(int num1 , int num2 , int[] nums) {int temp = nums[num1];nums[num1] = nums[num2];nums[num2] = temp;}
}

分治 - 归并

核心思想:   将一个问题分成若干个规模较小的子问题,分别求解后,再将子问题的结果合并,得到原问题的解。归并排序的核心步骤分为两个部分:“分”和“合”。

归并排序

:. - 力扣(LeetCode)

 public int[] sortArray(int[] nums) {sort(nums , 0 , nums.length - 1);return nums;}private void sort(int[] nums , int left , int right) {if(left >= right) return;//不断递归,将数组分割成俩部分,对两部分别再进行分割,直到每一部只剩下一个元素 , 俩俩进行合并int mid = left + (right - left) / 2;sort(nums , left , mid);sort(nums , mid + 1 , right);sortHelper(nums , left , mid , right);//合并的逻辑}//合并的俩个数组分别已经有序 , 建立一个新数组,设置俩个指针对俩个数组进行比较赋值到新数组上,使新数组比较//不要直接再原数组上进行比较交换 , 会打乱数组的有序性 , 将问题复杂化private void sortHelper(int[] nums , int left , int mid , int right) {int l = left;int r = mid + 1;int[] temp = new int[right - left + 1];int cur = 0;while(l <= mid && r <= right) {while(l <= mid && nums[l] <= nums[r]) temp[cur ++] = nums[l ++];while(r <= right && nums[r] <= nums[l]) temp[cur ++] = nums[r ++];}if(l <= mid){while(l <= mid)temp[cur ++] = nums[l ++];}if(r <= right) {while(r <= right) temp[cur ++] = nums[r ++];}for(int i = 0;i < temp.length;i ++) {nums[left + i] = temp[i];}}

优化 : 在进行合并时创建一个全局的,与原数组等大小的临时数组 , 这样就能避免每次进行合并时创建数组的开销.

例题

统计逆序对:  . - 力扣(LeetCode)

在上述归并的逻辑上加上 数组间统计逆序对 的逻辑即可

class Solution {//在进行数组之间合并排序之前加上一个统计数组间逆序队的逻辑`即可public int reversePairs(int[] record) {return sort(record , 0 , record.length - 1);}private int sort(int[] nums  , int left , int right) {if(left >= right) return 0;int mid = left + (right - left) / 2;int num1 = sort(nums , left , mid);int num2 = sort(nums , mid + 1 , right);int num3 = sortHelper(nums , left , mid , right);return (num1 + num2 + num3);}private int sortHelper(int[] nums ,int left ,int mid , int right){int l = left;int r = mid + 1;int count = 0;int[] model = new int[right - left + 1];int cur = 0;while(l <= mid && r <= right){while(l <= mid && nums[l] <= nums[r]) model[cur ++] = nums[l ++];while(r <= right && nums[r] < nums[l]){count += mid - l + 1;//统计逆序对; 因为合并的俩个数组已经分别有序,所以只需要统计数组间即可model[cur ++] = nums[r ++];}}while(l <= mid) model[cur ++] = nums[l ++];while(r <= right) model[cur ++] = nums[r ++];for(int i = 0;i < model.length;i ++) {nums[left + i] = model[i];}return count;}
}

右侧小于自己的数:. - 力扣(LeetCode)

首先:这道题使用暴力求解一定会超时

这道题进行归并的问题是: 归并排序后会进行元素交换, 交换后元素顺序被打乱  , 我们在进行合并数组时统计出来右侧小于当前元素的数后不知道这个元素的原始下标 .  所以这道题相比于上面求逆序对 , 需要多维护一个存储元素下标的数组.  原数组元素顺序改变时 , 这个存储下标的数组也随之进行改变 , 这样,我们就能通过nums中元素的下标拿到当前元素的初始位置 .

class Solution {private int[] indexMoel;//存储每个元素的原始位置 , 随着nums元素交换而交换,nums元素下标对应到indexModel上就是初始元素的位置,通过初始元素位置在dest上进行数量更新private int[] dest;//存储目标元素private int[] numsTemp;//使用全局数组进行合并,避免每次合并创建临时数组的开销private int[] indexTemp;public List<Integer> countSmaller(int[] nums) {indexMoel = new int[nums.length];numsTemp = new int[nums.length];indexTemp = new int[nums.length];dest = new int[nums.length];for(int i = 0;i < nums.length;i ++) {indexMoel[i] = i;}sort(nums , 0 , nums.length - 1);List<Integer> list = new ArrayList<>();for(int i = 0;i < dest.length;i ++) {list.add(dest[i]);}return list;}private void sort(int[] nums , int left , int right) {if(left >= right) return;int mid = left + (right - left) / 2;sort(nums , left , mid);sort(nums , mid + 1 , right);sortHelper(nums , left , mid , right);}private void sortHelper(int[] nums , int left , int mid , int right) {int l = left;int r = mid + 1;int cur1 = 0;int cur2 = 0;//降序排序 , 更好统计while(l <= mid && r <= right) {if(nums[l] > nums[r]) {dest[indexMoel[l]] += right - r + 1;//通过indexmodel拿到当前元素的初始位置进行统计numsTemp[cur1 ++] = nums[l];indexTemp[cur2 ++] = indexMoel[l ++];//indexModel随着nums的交换而交换}else {numsTemp[cur1 ++] = nums[r];indexTemp[cur2 ++] = indexMoel[r ++];}}while(l <= mid){numsTemp[cur1 ++] = nums[l];indexTemp[cur2 ++] = indexMoel[l ++];}while(r <= right){numsTemp[cur1 ++] = nums[r];indexTemp[cur2 ++] = indexMoel[r ++];}for(int i = 0;i < cur1;i ++) {nums[i + left] = numsTemp[i];indexMoel[i + left] = indexTemp[i]; }}
}


http://www.ppmy.cn/news/1528891.html

相关文章

RAII技术

RAII&#xff08;Resource Acquisition Is Initialization&#xff09;是C中一种重要的资源管理技术&#xff0c;由C之父Bjarne Stroustrup提出。RAII的核心思想是通过对象的生命周期来管理资源&#xff0c;即在对象的构造函数中获取资源&#xff0c;在对象的析构函数中释放资源…

【Kubernetes】常见面试题汇总(二十五)

目录 73.我们所有人都知道&#xff0c;从单片到微服务的转变解决了开发方面的问题&#xff0c;但却增加了部署方面的问题。公司如何解决部署方面的问题&#xff1f; 74.考虑一家拼车公司希望通过同时扩展其平台来增加服务器数量,公司如何有效地实现这种资源分配&#xff1f; …

bug | pycharm社区版无sciview解决办法

一个程序运行多个图&#xff0c;plt.show()一次只弹出一个独立窗口&#xff0c;必须关掉一个才能显示下一张图&#xff0c;想找sciview却发现找不到&#xff0c;本来以为是新版pycharm的问题&#xff0c;后来才发现是community版根本没有sciview…不想换专业版了&#xff0c;研…

[C++进阶[六]]list的相关接口模拟实现

1.前言 本章重点 在list模拟实现的过程中&#xff0c;主要是感受list的迭代器的相关实现&#xff0c;这是本节的重点和难点。 2.list接口的大致框架 list是一个双向循环链表&#xff0c;所以在实现list之前&#xff0c;要先构建一个节点类 template <class T> struct L…

Unity 高亮插件Highlight Plus快速入门

通常你可能只是想简单的为某个物体高亮显示 我将介绍最简单快速的方法 如果你想了解更多 Unity 高亮插件HighlightPlus介绍-CSDN博客 情景一 如果你只是想某个物体被鼠标覆盖显示高亮效果,鼠标离开高亮效果消失的话,你甚至不需要写一句代码! 为物体添加这两个脚本(添加T…

开源 AI 智能名片小程序:开启内容营销新境界

摘要&#xff1a;本文深入探讨了在当今数字化时代&#xff0c;内容营销的重要性以及如何实现让用户主动找你的最佳效果。通过引入开源 AI 智能名片小程序这一创新工具&#xff0c;阐述了其在明确目标用户群体、迎合用户需求痛点和打造风格特色方面的独特优势&#xff0c;为企业…

【Qt】实现模拟触摸屏 上下滑动表格 的两种方式

QScroller Qt QTableWidget 触摸屏上滑动效果 代码 // 创建 QScroller 对象并与 tableWidget 关联.QScroller *pScroller QScroller::scroller(ui->tableView);// 捕获滚动手势.pScroller->grabGesture(ui->tableView, QScroller::LeftMouseButtonGesture);// 设置…

javascript数据结构

在 JavaScript 中&#xff0c;数据结构的选择和实现对于编写高效、可维护的代码至关重要。JavaScript 提供了一系列内置的数据结构&#xff0c;同时也支持自定义复杂的数据结构。以下是 JavaScript 中常用的一些数据结构及其基本介绍&#xff1a; 内置数据结构 1. 数组&#…