0.分治

分而治之

1.顏色分類

75. 顏色分類 - 力扣（LeetCode）

給定一個包含紅色、白色和藍色、共?n?個元素的數組?nums?，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。

我們使用整數?0、?1?和?2?分別表示紅色、白色和藍色。

必須在不使用庫內置的 sort 函數的情況下解決這個問題。

示例 1：

輸入：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]

示例 2：

輸入：nums = [2,0,1]
輸出：[0,1,2]

class Solution {public void sortColors(int[] nums) {int n=nums.length;int left=-1,right=n,i=0;while(i<right){//i要掃描完if(nums[i]==0){swap(nums,++left,i++);}else if(nums[i]==2){swap(nums,--right,i);}else{i++;}}}public void swap(int[] nums,int x,int y){int tmp=nums[x];nums[x]=nums[y];nums[y]=tmp;}
}

2.快速排序

排序數組

給你一個整數數組?nums，請你將該數組升序排列。

class Solution {public int[] sortArray(int[] nums) {qsort(nums,0,nums.length-1);return nums;}public void qsort(int[] nums,int l,int r){if(l>=r){return;}//數組分為三塊//1.隨機在區間內選值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{swap(nums,--right,i);}}//[l,left],[left+1,right-1],[right,r]qsort(nums,l,left);qsort(nums,right,r);}public void swap(int[] nums,int x,int y){int tmp=nums[x];nums[x]=nums[y];nums[y]=tmp;}
}

3.數組中的第k個最大元素

215. 數組中的第K個最大元素 - 力扣（LeetCode）

給定整數數組?nums?和整數?k，請返回數組中第?k?個最大的元素。

請注意，你需要找的是數組排序后的第?k?個最大的元素，而不是第?k?個不同的元素。

你必須設計并實現時間復雜度為?O(n)?的算法解決此問題。

示例 1:

輸入: [3,2,1,5,6,4], k = 2
輸出: 5

示例?2:

輸入: [3,2,3,1,2,4,5,5,6], k = 4
輸出: 4

class Solution {public int findKthLargest(int[] nums, int k) {return qsortchoice(nums, 0, nums.length - 1, k);}public int qsortchoice(int[] nums, int l, int r, int k) {while (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 {swap(nums, --right, i);}}// 快速選擇的算法，分情況討論int b = right - left - 1, c = r - right + 1;if (c >= k) {return qsortchoice(nums, right, r, k);} else if (b + c >= k) {return key;} else {return qsortchoice(nums, l, left, k - b - c);}}public void swap(int[] nums, int x, int y) {int tmp = nums[x];nums[x] = nums[y];nums[y] = tmp;}
}

4.最小的K個數

class Solution {public int[] inventoryManagement(int[] nums, int k) {qsortchoice(nums, 0, nums.length - 1, k);int[] ret=new int[k];for(int i=0;i<k;i++){ret[i]=nums[i];}return ret;}public void qsortchoice(int[] nums, int l, int r, int k) {while (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 {swap(nums, --right, i);}}// 快速選擇的算法，分情況討論int a=left-l+1,b=right-1-left-1+1;if (a>k) {qsortchoice(nums, l, left, k);} else if (a + b >= k) {return;} else {qsortchoice(nums, right,r, k - a-b);}}public void swap(int[] nums, int x, int y) {int tmp = nums[x];nums[x] = nums[y];nums[y] = tmp;}
}

5.歸并排序

912. 排序數組 - 力扣（LeetCode）

在遞歸的時候如果總是需要new一個變量，這是我們可以把這個變量作為全局變量。

class Solution {int[] tmp;//定義全局變量，就不用反復new了public int[] sortArray(int[] nums) {tmp=new int[nums.length];mergeSort(nums,0,nums.length-1);return nums;}public void mergeSort(int[] nums,int left,int right){if(left>=right){return;}//1.根據中間點劃分區間int mid=(left+right)/2;//[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++];}//處理沒有遍歷完的數組while(cur1<=mid){tmp[i++]=nums[cur1++];}while(cur2<=right){tmp[i++]=nums[cur2++];}//還原到nums數組上for(int j=left;j<=right;j++){nums[j]=tmp[j-left];}}
}

6.數組中的逆序對

LCR 170. 交易逆序對的總數 - 力扣（LeetCode）

class Solution {int[] tmp;public int reversePairs(int[] record) {int n=record.length;tmp=new int[n];return mergeSort(record,0,n-1);}public int mergeSort(int[] nums,int left,int right){while(left>=right){return 0;}int ret=0;//選擇一個中間點，將數組進行劃分int mid=(left+right)/2;//[left,mid][mid+1,right]//2.左半部分的個數+右半部分的個數+排序ret=ret+mergeSort(nums,left,mid);ret=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=ret+mid-cur1+1;tmp[i++]=nums[cur2++];}}//4.處理一下后面的排序while(cur1<=mid){tmp[i++]=nums[cur1++];}while(cur2<=right){tmp[i++]=nums[cur2++];}for(int j=left;j<=right;j++){nums[j]=tmp[j-left];}return ret;}
}

?7.計算右側?于當前元素的個數(難點)

315. 計算右側小于當前元素的個數 - 力扣（LeetCode）

class Solution {int[] ret;int[] index; // 標記 nums 中當前元素的原始下標int[] tmpIndex;int[] tmpNums;public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tmpIndex = new int[n];tmpNums = new int[n];// 初始化 index 數組for (int i = 0; i < n; i++) {index[i] = i;}mergeSort(nums, 0, n - 1);List<Integer> l = new ArrayList<Integer>();for (int x : ret) {l.add(x);}return l;}public void mergeSort(int[] nums, int left, int right) {if (left >= right) {return;}// 1. 根據中間元素劃分區間int mid = (left + right) / 2;// [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++];}for (int j = left; j <= right; j++) {nums[j] = tmpNums[j - left];index[j] = tmpIndex[j - left];}}
}

?8.翻轉對

給定一個數組?nums?，如果?i < j?且?nums[i] > 2*nums[j]?我們就將?(i, j)?稱作一個重要翻轉對。

你需要返回給定數組中的重要翻轉對的數量。

示例 1:

輸入: [1,3,2,3,1]
輸出: 2

示例 2:

輸入: [2,4,3,5,1]
輸出: 3

注意:

1. 給定數組的長度不會超過50000。
2. 輸入數組中的所有數字都在32位整數的表示范圍內。

?

class Solution {int[] tmp;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return mergeSort(nums, 0, n - 1);}public int mergeSort(int[] nums, int left, int right) {if (left >= right)return 0;int ret = 0;// 1. 根據中間元素，將區間分成兩部分int mid = (left + right) / 2;// [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 = 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++];for (int j = left; j <= right; j++)nums[j] = tmp[j];return ret;}
}