优选算法专题7：分治

分治目录分治试题1颜色分类算法原理代码编写试题2排序数组快排算法原理代码编写试题3数组中的第K个最大元素算法原理代码编写试题4最小的k个数算法原理代码编写试题5排序数组归并算法原理代码编写试题6数组中的逆序对算法原理代码编写试题7计算右侧小于当前元素的个数算法原理代码编写试题8翻转对算法原理代码编写试题1颜色分类算法原理分治分而治之解法三指针代码编写个人版本class Solution { public: void sortColors(vectorint nums) { int left -1, right nums.size(), i 0; while(i right) { if(nums[i] 0) { swap(nums[left], nums[i]); } else if(nums[i] 1) { i; } else { swap(nums[--right], nums[i]); } } } };标准版本class Solution { public: void sortColors(vectorint nums) { int n nums.size(); int left -1, right n, i 0; while(i right) { if(nums[i] 0) swap(nums[left], nums[i]); else if(nums[i] 1) i; else swap(nums[--right],nums[i]); } } };试题2排序数组快排算法原理解法快速排序代码编写class Solution { public: vectorint sortArray(vectorint nums) { srand(time(NULL)); qsort(nums,0,nums.size() - 1); return nums; } void qsort(vectorint nums,int l,int r) { if(l r) { return; } //数组分成三块 int key getRandom(nums,l,r); int i l,left l - 1,right r 1; while(i right) { if(nums[i] key) { swap(nums[left],nums[i]); } else if(nums[i] key) { i; } else { swap(nums[--right],nums[i]); } } //[1,left][left 1,right - 1][right,r] qsort(nums,l,left); qsort(nums,right,r); } int getRandom(vectorint nums,int left,int right) { int r rand(); return nums[r % (right - left 1) left]; } };试题3数组中的第K个最大元素算法原理解法一堆排序O(NlogN)解法二快速选择算法O(N)代码编写class Solution { public: int findKthLargest(vectorint nums, int k) { srand(time(NULL)); return qsort(nums,0,nums.size() - 1,k); } int qsort(vectorint nums,int l,int r,int k) { if(l r) { return nums[l]; } //1. 随机选择基准元素 int key getRandom(nums,l,r); //2. 根据基准元素将数组分三块 int left l - 1,right r 1,i l; while(i right) { if(nums[i] key) { swap(nums[left],nums[i]); } else if(nums[i] key) { i; } else { swap(nums[--right],nums[i]); } } //3. 分情况讨论 int c r - right 1; int b ( right - 1 ) - ( left 1 ) 1; if(c k) { return qsort(nums,right,r,k); } else if(b c k) { return key; } else { return qsort(nums,l,left,k - b - c); } } int getRandom(vectorint nums,int left,int right) { return nums[rand() % (right - left 1) left]; } };试题4最小的k个数算法原理解法一排序O(NlogN)解法二大根堆O(NlogK)解法三快速选择算法O(N)随机选择基准元素数组分三块代码编写class Solution { public: vectorint inventoryManagement(vectorint nums, int k) { srand(time(NULL)); qsort(nums, 0, nums.size() - 1, k); return {nums.begin(), nums.begin() k}; } void qsort(vectorint nums, int l,int r,int k) { if(l r) { return; } //1. 随机选择一个基准元素 int key getRandom(nums, l, r); //2.数组分三块 int left l - 1,right r 1,i l; while(i right) { if(nums[i] key) { swap(nums[left],nums[i]); } else if(nums[i] key) { i; } else { swap(nums[--right],nums[i]); } } // [l,left][left1,right-1][right,r] int a left - l 1; int b right - left - 1; if(a k) { qsort(nums, l, left, k); } else if(a b k) { return; } else { qsort(nums, right, r, k - a - b); } } int getRandom(vectorint nums, int l,int r) { return nums[rand() % (r - l 1) l]; } };试题5排序数组归并算法原理代码编写class Solution { vectorint tmp; public: vectorint sortArray(vectorint nums) { tmp.resize(nums.size()); mergeSort(nums, 0, nums.size() - 1); return nums; } void mergeSort(vectorint nums, int left, int right) { if(left right) { return; } //1. 选择中间点划分区间 int mid (left right) 1; //[left, mid] [mid 1, right] //2. 排序左右区间 mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); //3. 合并两个有序数组 int cur1 left,cur2 mid 1, i 0; while(cur1 mid cur2 right) { tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2]; } //4. 处理没有遍历完的数组 while(cur1 mid) { tmp[i] nums[cur1]; } while(cur2 right) { tmp[i] nums[cur2]; } //还原 for(int i left; i right; i) { nums[i] tmp[i - left]; } } };试题6数组中的逆序对算法原理解法一暴力枚举两层for循环解法二归并排序代码编写class Solution { int tmp[50010]; public: int reversePairs(vectorint nums) { return mergeSort(nums, 0, nums.size() - 1); } int mergeSort(vectorint nums, int left, int right) { if(left right) { return 0; } int ret 0; //1. 找中间点将数组分成两份 int mid (left right) 1; //[left, mid][mid 1, right] //2. 左边个数 排序 右边个数 排序 ret mergeSort(nums, left, mid); ret mergeSort(nums, mid 1, right); //3. 一左一右个数 int cur1 left, cur2 mid 1,i 0; while(cur1 mid cur2 right) { if(nums[cur1] nums[cur2]) { tmp[i] nums[cur1]; } else { ret mid - cur1 1; tmp[i] nums[cur2]; } } //4. 处理剩余排序 while(cur1 mid) { tmp[i] nums[cur1]; } while(cur2 right) { tmp[i] nums[cur2]; } //5. 还原 for(int j left; j right; j) { nums[j] tmp[j - left]; } return ret; } };试题7计算右侧小于当前元素的个数算法原理代码编写class Solution { vectorint ret; vectorint index; int tmpNums[500010]; int tmpIndex[500010]; public: vectorint countSmaller(vectorint nums) { int n nums.size(); ret.resize(n); index.resize(n); //初始化index数组 for(int i 0; i n; i) { index[i] i; } mergeSort(nums, 0, n - 1); return ret; } void mergeSort(vectorint nums, int left, int right) { if(left right) { return; } //1. 根据中间元素划分区间 int mid (right left) 1; //[left, mid][mid 1, right] //2. 先处理左右两部分 mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); //3. 处理一左一右 int cur1 left, cur2 mid 1, i 0; while(cur1 mid cur2 right) { if(nums[cur1] nums[cur2]) { tmpNums[i] nums[cur2]; tmpIndex[i] index[cur2]; } else { ret[index[cur1]] right - cur2 1; tmpNums[i] nums[cur1]; tmpIndex[i] index[cur1]; } } //4. 处理剩下排序 while(cur1 mid) { tmpNums[i] nums[cur1]; tmpIndex[i] index[cur1]; } while(cur2 right) { tmpNums[i] nums[cur2]; tmpIndex[i] index[cur2]; } //5. 还原 for(int j left; j right; j) { nums[j] tmpNums[j - left]; index[j] tmpIndex[j - left]; } } };试题8翻转对算法原理解法一暴力枚举解法二分治代码编写降序策略class Solution { int tmp[50010]; public: int reversePairs(vectorint nums) { return mergeSort(nums, 0, nums.size() - 1); } int mergeSort(vectorint nums, int left, int right) { if(left right) { return 0; } int ret 0; //1. 找中间点划分区间 int mid (left right) 1; //2. 计算左右两侧翻转对 ret mergeSort(nums, left, mid); ret mergeSort(nums,mid 1, right); //3. 计算一左一右翻转对数量 int cur1 left, cur2 mid 1, i left; while(cur1 mid) { while(cur2 right nums[cur2] nums[cur1] / 2.0) { cur2; } if(cur2 right) { break; } ret right - cur2 1; cur1; } //4. 合并两个有序数组 cur1 left, cur2 mid 1; while(cur1 mid cur2 right) { tmp[i] nums[cur1] nums[cur2] ? nums[cur2] : nums[cur1]; } while(cur1 mid) { tmp[i] nums[cur1]; } while(cur2 right) { tmp[i] nums[cur2]; } //5. 还原 for(int j left; j right; j) { nums[j] tmp[j]; } return ret; } };升序策略class Solution { int tmp[50010]; public: int reversePairs(vectorint nums) { return mergeSort(nums, 0, nums.size() - 1); } int mergeSort(vectorint nums, int left, int right) { if(left right) { return 0; } int ret 0; //1. 找中间点划分区间 int mid (left right) 1; //2. 计算左右两侧翻转对 ret mergeSort(nums, left, mid); ret mergeSort(nums,mid 1, right); //3. 计算一左一右翻转对数量 int cur1 left, cur2 mid 1, i left; while(cur2 right) { while(cur1 mid nums[cur2] nums[cur1] / 2.0) { cur1; } if(cur1 mid) { break; } ret mid - cur1 1; cur2; } //4. 合并两个有序数组 cur1 left, cur2 mid 1; while(cur1 mid cur2 right) { tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2]; } while(cur1 mid) { tmp[i] nums[cur1]; } while(cur2 right) { tmp[i] nums[cur2]; } //5. 还原 for(int j left; j right; j) { nums[j] tmp[j]; } return ret; } };