优选算法的妙思之流：分治——快排专题

专栏算法的魔法世界个人主页手握风云目录一、快速排序二、例题讲解2.1. 颜色分类2.2. 排序数组2.3. 数组中的第K个最大元素2.4. 库存管理 III一、快速排序分治简单理解为“分而治之”将一个大问题划分为若干个子问题直到这个子问题能够快速解决。我们之前的快速排序是选出一个数作为基准值然后将一个数组划分为两个子序列一个序列基准值另一个基准值。但这种算法在数据特别大的时候是会超时的。所以我们这里要使用更优秀的三块划分和随机选择基准元素的算法。二、例题讲解2.1. 颜色分类这道题我们可以参照移动零里面的划分策略。移动零里面是利用双指针将数组分为0区域和非0区域这道题我们也可以使用三个指针left、right、i来将其划分为0、1、2区域。其中i用来遍历数组left用来标记0区域的最右侧right用来标记2区域的最左侧。接下来进行分类讨论如果nums[i]0我们让nums[left1]与nums[i]进行交换然后ileft就能保证[left1,i-1]区间还都是1还可能有一种极端情况就是ileft1自身与自身进行交换还是得需要left和i综上我们就可以写成nums[left]与nums[i]进行交换。如果nums[i]1我们直接就可以i就可以。如果nums[i]2时right的移动也可以参照上面left的处理--right但i不能因为i右侧是未遍历的区间如果i就会跳过这个元素。当iright时结束循环。完整代码实现class Solution { public void sortColors(int[] nums) { int left -1, right nums.length, i 0; while (i right) { if (nums[i] 0) swap(nums, left, i); else if (nums[i] 1) i; else if (nums[i] 2) swap(nums, --right, i); } } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }2.2. 排序数组这道题如果我们直接采用之前的快排思想是会超时的因为如果数组里的元素都等于基准值key这样数组元素就会跑到数组的最右侧导致时间复杂度会退化成。我们接下来利用数组分三块的思想将其划分为3个区域keykeykey。这样当基准值都等于key时时间复杂度直接降为。接下来就是如何随机选择基准值。我们需要在数组下标中等概率地选择一个下标那么我们就可以利用随机数种子利用公式r%(right-left1)left求出随机下标。完整代码实现class Solution { public int[] sortArray(int[] nums) { Quicksort(nums, 0, nums.length - 1); return nums; } private void Quicksort(int[] nums, int l, int r) { if (l r) return;//作为递归结束的条件 //数组分三块 int key nums[new Random().nextInt(r - l 1) l]; int left l - 1, right r 1, i l; while (i right) { if (nums[i] key) swap(nums, left, i); else if (nums[i] key) i; else if (nums[i] key) swap(nums, --right, i); } Quicksort(nums, l, left); Quicksort(nums, right, r); } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }2.3. 数组中的第K个最大元素因为这道题让我们用时间复杂度为所以我们的思路很明显要使用快速选择排序也就是上一题的数组分三块与随机选择基准元素。那么这个第K大的元素就有可能落在三个区域内我们设三个区域的元素个数分别为a、b、c。如果ck那我们就直接去key的这个区域去寻找如果bck就直接返回key如果前两个都不成立就去key这个区间去寻找第k-b-c大的元素。完整代码实现class Solution { public int findKthLargest(int[] nums, int k) { return Quicksort(nums, 0, nums.length - 1, k); } private int Quicksort(int[] nums, int l, int r, int k) { if (l r) return nums[l]; //随机选择基准元素 int key nums[new Random().nextInt(r - l 1) l]; //根据基准元素把数组分为三块 int left l - 1, right r 1, i l; while (i right) { if (nums[i] key) swap(nums, left, i); else if (nums[i] key) i; else if (nums[i] key) swap(nums, --right, i); } //分类讨论 //区间:[l,left],[left1,right-1],[right,r] int b right - left - 1, c r - right 1; if (c k) return Quicksort(nums, right, r, k); else if (b c k) return key; else return Quicksort(nums, l, left, k - b - c); } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }2.4. 库存管理 III题目就是求数组中的最小的cnt个数。第一种解法可以使用Arrays.sort()方法来对数组进行排序找出前k个元素第二种解法利用大根堆创建一个大小为k的大根堆将数组的前k个元素丢进大根堆中然后再将数组剩余的元素与堆顶元素比较如果小就交换并调整堆最后堆里面就是最小的k个数第三个解法就是快速选择算法。第一种解法的时间复杂度为第二种解法的时间复杂度为第三中解法的时间复杂度为。按照上一题的思路将数组分为三块三个区间内元素的个数分别为a、b、c。如果acnt那么我们只需要去key的区间去寻找如果abcnt此时的cnt一定是大于a的那么最小的cnt个数一定位于左侧两个区间而中间区间又都是等于key的所以不需要递归直接如果前两个都不成立直接去最右侧的区间去寻找第cnt-a-b个元素。完整代码实现class Solution { public int[] inventoryManagement(int[] stock, int cnt) { Quicksort(stock,0,stock.length - 1,cnt); int[] ret new int[cnt]; for (int i 0; i cnt; i) { ret[i] stock[i]; } return ret; } private void Quicksort(int[] nums, int l, int r, int k) { if(l r) return; //随机获取基准元素 int key nums[new Random().nextInt(r - l 1) l]; int left l - 1,right r 1,i l; //数组分三块 while(i right){ if(nums[i] key) swap(nums,left,i); else if (nums[i] key) i; else if (nums[i] key) swap(nums,--right,i); } //分类讨论 int a left - l 1,b right - left - 1; if(a k) Quicksort(nums,l,left,k); else if (a b k) return; else Quicksort(nums,right,r,k - a - b); } private void swap(int[] nums, int i, int j) { int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } }