算法: 分治题目练习

---

分治

颜色分类

把数组分成四段:

1. 元素为 0
2. 元素为 1
3. 未划分
4. 元素为 2

不是很难~

    private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}public void sortColors(int[] nums) {int k = nums.length - 1, i = 0, f = -1;while (i <= k) {if (nums[i] == 2) {swap(nums, i, k--);} else if (nums[i] == 0) {swap(nums, i++, ++f);} else {i++;}}}

排序数组 (快排)

写一个快排~
取随机数时卡了一下.

坑;

• 快排不优化一下过不了~

private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}private int quick(int[] nums, int left, int right) {if (left >= right) return left;int partation = nums[new Random().nextInt(right - left + 1) + left];for (int i = left; i <= right; ) {if (nums[i] < partation) {swap(nums, i++, left++);} else if (nums[i] > partation) {swap(nums, i, right--);} else {i++;}}return left;}private void quickSort(int[] nums, int start, int end) {if (start >= end) return;int pos = quick(nums, start, end);quickSort(nums, start, pos - 1);quickSort(nums, pos + 1, end);}public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length - 1);return nums;}

题解代码更好~

class Solution {private void swap(int[] nums,int i,int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}private void quickSort(int[] nums,int start,int end) {if(start >= end) return;int pos = nums[new Random().nextInt(end-start+1)+start];int left = start - 1,right = end + 1,i = start;while(i < right) {if(nums[i] < pos) swap(nums,++left,i++);else if(nums[i] > pos) swap(nums,i,--right);else i++;}quickSort(nums,start,left);quickSort(nums,right,end);}public int[] sortArray(int[] nums) {quickSort(nums,0,nums.length-1);return nums;}
}

数组中的第K个最大元素

做这道题时,我因为边界问题卡了半天,后来发现自己把区间范围搞错了,浪费了10多分钟.

• [start , left] : 小于 pos
• [left + 1 , right - 1] : 等于 pos
• [right , end] : 大于pos

private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}private int find(int[] nums, int k, int start, int end) {if (start >= end)return nums[start];int left = start - 1, i = start, right = end + 1;int pos = nums[new Random().nextInt(end - start + 1) + start];while (i < right) {if (nums[i] < pos)swap(nums, i++, ++left);else if (nums[i] > pos)swap(nums, i, --right);elsei++;}if (end - right + 1 >= k) {return find(nums, k, right, end);} else if (end - left >= k) {return nums[right - 1];} else {return find(nums, k - (end - left), start, left);}}public int findKthLargest(int[] nums, int k) {return find(nums, k, 0, nums.length - 1);}

库存管理 III

跟上一题很像.

主要是最后的分段条件需要想想,前面的都一样~

class Solution {private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}private void qsort(int[] stock, int cnt, int start, int end) {if (start >= end)return;int left = start - 1, i = start, right = end + 1;int pos = stock[new Random().nextInt(end - start + 1) + start];while (i < right) {if (stock[i] < pos)swap(stock, i++, ++left);else if (stock[i] > pos)swap(stock, i, --right);elsei++;}if (left - start + 1 > cnt) {qsort(stock, cnt, start, left);} else if (right - start >= cnt) {return;} else {qsort(stock, cnt - (right - start), right, end);}}public int[] inventoryManagement(int[] stock, int cnt) {qsort(stock, cnt, 0, stock.length - 1);return Arrays.copyOf(stock, cnt);}
}

排序数组 (归并排序)

归并排序很简单~

1. 把数组分成两个区间.
2. 分别给左右两个区间排序
3. 合并两个有序数组
4. 把排序后的结果还原到数组中

class Solution {// 辅助数组private int[] arr;private void mergeSort(int[] nums, int start, int end) {if (start >= end)return;// 把数组划分成两个区间 [start,mid] [mid+1,end]// 把左右区间排序int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);// 合并两个有序数组int left = start, right = mid + 1, k = 0;while (left <= mid && right <= end) {if (nums[left] < nums[right]) {arr[k++] = nums[left++];} else {arr[k++] = nums[right++];}}while (left <= mid) {arr[k++] = nums[left++];}while (right <= end) {arr[k++] = nums[right++];}int i = 0;while (start <= end) {nums[start++] = arr[i++];}}public int[] sortArray(int[] nums) {// 给辅助数组申请一块空间arr = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}
}

题解代码:

class Solution {// 辅助数组private int[] arr;private void mergeSort(int[] nums, int start, int end) {if (start >= end)return;// 把数组划分成两个区间 [start,mid] [mid+1,end]// 把左右区间排序int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);// 合并两个有序数组int left = start, right = mid + 1, k = 0;while (left <= mid && right <= end) {arr[k++] = nums[left] < nums[right] ? nums[left++] : nums[right++];}while (left <= mid) {arr[k++] = nums[left++];}while (right <= end) {arr[k++] = nums[right++];}// 还原for (int i = start; i <= end; i++)nums[i] = arr[i - start];}public int[] sortArray(int[] nums) {// 给辅助数组申请一块空间arr = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}
}

交易逆序对的总数

十分甚至九分的不好理解.
思路很简单

1. 把数组分成两块, [left , mid] [mid + 1 , end]
2. 在[left , mid] 上用递归寻找有多少个逆序对 + 排序
3. 在[mid + 1 , end] 上用递归寻找有多少个逆序对 + 排序
4. 在[left , mid]中选择一个数, 在[mid + 1 , end]中选择一个数,寻找逆序对+排序

问题在于怎么把寻找逆序对和排序结合起来.

不太明白啥时候用升序,啥时候用降序.

• 升: 求当前元素的前面有多少个元素比我大
• 降: 求当前元素的后面有多少个元素比我小

在写递归的时候,你要相信这个函数能做到它该做到的功能.只管往下写.

升序版本:

class Solution {private int tmp[];public int merge(int[] arr, int start, int end) {int sum = 0;if (start >= end)return sum;int mid = start + (end - start) / 2;// 划分区间 [left , mid] [mid + 1 , end]sum += merge(arr, start, mid);sum += merge(arr, mid + 1, end);// 升序int left = start, right = mid + 1, k = 0;while (left <= mid && right <= end) {if (arr[left] <= arr[right]) {tmp[k++] = arr[left++];} else {tmp[k++] = arr[right++];sum += mid - left + 1;}}// 归并排序收尾while (left <= mid)tmp[k++] = arr[left++];while (right <= end)tmp[k++] = arr[right++];for (int i = start; i <= end; i++) {arr[i] = tmp[i - start];}return sum;}public int reversePairs(int[] record) {tmp = new int[record.length];return merge(record, 0, record.length - 1);}
}

降序版本:

class Solution {private int tmp[];public int merge(int[] arr, int start, int end) {int sum = 0;if (start >= end)return sum;int mid = start + (end - start) / 2;sum += merge(arr, start, mid);sum += merge(arr, mid + 1, end);int left = start, right = mid + 1, k = 0;while (left <= mid && right <= end) {if (arr[left] <= arr[right]) {tmp[k++] = arr[right++];} else {tmp[k++] = arr[left++];sum += end - right + 1;}}while (left <= mid)tmp[k++] = arr[left++];while (right <= end)tmp[k++] = arr[right++];for (int i = start; i <= end; i++) {arr[i] = tmp[i - start];}return sum;}public int reversePairs(int[] record) {tmp = new int[record.length];return merge(record, 0, record.length - 1);}
}

计算右侧小于当前元素的个数

跟上一题很像, 但是题目要求返回 List<Integer> , 在上一个题目的基础上,还需要记录下来原始数组中元素对应的下标.用一个数组index来记录就行,但是arr中的元素咋交换,index就咋交换.

我在最后的int[]转List<Integer>想了一会,能不能一行解决,没想到,不会~

坑:

• 需要创建两个辅助数组,一个给arr用,一个给index用. 而且需要同步交换.
• ret[index[left]] += end - right + 1; 中间是 += 而不是 =

class Solution {private int[] tmpNums;private int[] tmpIndex;private void merge(int[] arr, int start, int end, int[] ret, int[] index) {if (start >= end)return;// 划分区间 + 排序int mid = start + (end - start) / 2;merge(arr, start, mid, ret, index);merge(arr, mid + 1, end, ret, index);// 一左一右int left = start, right = mid + 1, k = 0;while (left <= mid && right <= end) {if (arr[left] <= arr[right]) {// 同步交换tmpNums[k] = arr[right];tmpIndex[k++] = index[right++];} else {// 计入结果 + 同步交换ret[index[left]] += end - right + 1;tmpNums[k] = arr[left];tmpIndex[k++] = index[left++];}}// 归并收尾while (left <= mid) {tmpNums[k] = arr[left];tmpIndex[k++] = index[left++];}while (right <= end) {// 同步交换tmpNums[k] = arr[right];tmpIndex[k++] = index[right++];}for (int i = start; i <= end; i++) {arr[i] = tmpNums[i - start];index[i] = tmpIndex[i - start];}}public List<Integer> countSmaller(int[] nums) {int n = nums.length;List<Integer> list = new ArrayList<>();tmpNums = new int[n];tmpIndex = new int[n];// 记录下标int[] index = new int[n];// 初始化 index 数组for (int i = 0; i < n; i++) {index[i] = i;}int[] ret = new int[n];merge(nums, 0, n - 1, ret, index);for (int x : ret) {list.add(x);}return list;}
}

翻转对

把归并和求sum分开写就OK.

降序版本:

class Solution {int[] tmp;private int merge(int[] nums, int start, int end) {int sum = 0;if (start >= end)return sum;int mid = start + (end - start) / 2;sum += merge(nums, start, mid);sum += merge(nums, mid + 1, end);// 求sumint left = start, right = mid + 1, k = 0;while (left <= mid && right <= end) {if (nums[left] <= (long) 2 * nums[right]) {right++;} else {sum += end - right + 1;left++;}}// 归并left = start;right = mid + 1;while (left <= mid && right <= end) {if (nums[left] <= nums[right]) {tmp[k++] = nums[right++];} else {tmp[k++] = nums[left++];}}while (left <= mid) {tmp[k++] = nums[left++];}while (right <= end) {tmp[k++] = nums[right++];}for (int i = start; i <= end; i++) {nums[i] = tmp[i - start];}return sum;}public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}
}

升序版本:

class Solution {int[] tmp;private int merge(int[] nums, int start, int end) {int sum = 0;if (start >= end)return sum;int mid = start + (end - start) / 2;sum += merge(nums, start, mid);sum += merge(nums, mid + 1, end);int left = start, right = mid + 1, k = 0;while (left <= mid && right <= end) {if (nums[left] <= (long) 2 * nums[right]) {left++;} else {sum += mid - left + 1;right++;}}left = start;right = mid + 1;while (left <= mid && right <= end) {if (nums[left] <= nums[right]) {tmp[k++] = nums[left++];} else {tmp[k++] = nums[right++];}}while (left <= mid) {tmp[k++] = nums[left++];}while (right <= end) {tmp[k++] = nums[right++];}for (int i = start; i <= end; i++) {nums[i] = tmp[i - start];}return sum;}public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}
}

总结

• 下面的代码(快排主逻辑)多看几遍, 写熟.

  int left = start - 1, i = start, right = end + 1;// 快排优化: 指定一个随机数作为基准值
  int pos = arr[new Random().nextInt(end - start + 1) + start];while (i < right) {if (arr[i] < pos)swap(stock, i++, ++left);else if (arr[i] > pos)swap(arr, i, --right);elsei++;
  }
  

• 归并排序很简单~

  1. 把数组分成两个区间.
  2. 分别给左右两个区间排序.
  3. 合并两个有序数组.
  4. 把排序后的结果还原到数组中.

---

本文到这里就结束啦~