备注：
时间复杂度O(n^2)
冒泡排序
public class BubbleSort {
private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean isSwap = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
isSwap = true;
}
}
if (!isSwap) {
break;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} LC283 移动零
题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
public class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
// 1.非0元素往前放,index记录放的位置
for (int num : nums) {
if (num != 0) {
nums[index++] = num;
}
}
// 2.[index,n-1]放回0
for (int i = index; i < nums.length; i++) {
nums[i] = 0;
}
}
} 剑指45 拼接最小数字
题目:输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2] 输出: "102"
示例 2:
输入: [3,30,34,5,9] 输出: "3033459"
public class Solution {
public String minNumber(int[] nums) {
// 用list存储String
List<String> list = new ArrayList<>();
for (int num : nums) {
// 将nums中的值转换为String存储进list
list.add(String.valueOf(num));
}
// 拼接数组内所有元素使结果最小，本质上是排序
// 若字符串拼接 a + b > b + a，那么排序上 b < a;
list.sort((a, b) -> (a + b).compareTo(b + a));
// 用res接受结果字符串
StringBuilder res = new StringBuilder();
for (String str : list) {
res.append(str);
}
return res.toString();
}
} 选择排序
public class SelectionSort {
private static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr,i,minIndex );
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} LC215 找出第K个最大元素
题目：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
public class Solution {
// 选择排序法:找出K次最大值,返回即可
public int findKthLargest(int[] nums, int k) {
// 外层循环k次
for (int i = 0; i < k; i++) {
// 找最大值就行
int maxIndex = i;
for (int j = i + 1; j < nums.length; j++) {
maxIndex = nums[maxIndex] < nums[j] ? j : maxIndex;
}
swap(nums, i, maxIndex);
}
// 第一次最大值下标=1-1=0;
// 第K次最大值下标=k-1
return nums[k - 1];
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
插入排序
public class InsertionSort {
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j;
for (j = i; j - 1 >= 0 && temp < arr[j - 1]; j--) {
// 前面的数比temp都大,每个数都依次往后移
arr[j] = arr[j - 1];
}
// 空出的位置放temp
arr[j] = temp;
}
}
} LC147 对链表进行排序
题目:对链表进行插入排序
示例 1：
输入: 4->2->1->3 输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0 输出: -1->0->3->4->5
分析：[1,2,2,3,2]=>[1,2,2,2,3]
- 初始化：哑结点，last结点指向head，cur结点指向head.next
- cur进行遍历，联想[1,2,2,3,2]=>[1,2,2,2,3]交换的过程
public class Solution {
// 问题：链表的插入排序
public ListNode insertionSortList(ListNode head) {
if (head == null) {
return null;
}
// 哑结点
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode pre = head;
ListNode cur = head.next;
while (cur != null) {
// 依然有序,pre后移
if (pre.val <= cur.val) {
pre = pre.next;
} else {
// 倒序,初始化一个lastPre指向哑结点,从头找<=cur.val的最后一个结点的前一个结点
ListNode lastPre = dummyNode;
while (lastPre.next.val <= cur.val) {
lastPre = lastPre.next;
}
// 交换lastPre,pre,cur
pre.next = cur.next;
cur.next = lastPre.next;
lastPre.next = cur;
}
// cur移动到pre后面
cur = pre.next;
}
return dummyNode.next;
}
} 时间复杂度O(nlogn)
希尔排序
希尔排序是对插入排序的一种改进尝试，每次基于一定间隔的的两数进行排序，直到间隔为1再进行插入排序。
在合适步长下，为什么希尔排序可以将时间复杂度降到O(nlogn)？
- 希尔排序是按照间隔来插入排序，比直接插入排序相邻两个比较消除的逆序多会更多
public class ShellSort {
// 希尔排序
public static void shellSort(int[] arr) {
// 步长step
int step = arr.length / 2;
// 插入排序最低就是步长为1
while (step >= 1) {
// 以step为距离进行插入排序
for (int i = step; i < arr.length; i += step) {
int temp = arr[i];
int j;
for (j = i; j - step >= 0 && temp < arr[j - step]; j -= step) {
arr[j] = arr[j - step];
}
arr[j] = temp;
}
step /= 2;
}
}
// 插入排序:最后一步步长是1,不是0
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j;
for (j = i; j - 1 >= 0 && temp < arr[j - 1]; j--) {
arr[j] = arr[j - 1];
}
arr[j] = temp;
}
}
} LC506 相对名次
题目：给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（"Gold Medal", "Silver Medal", "Bronze Medal"）。
(注：分数越高的选手，排名越靠前。)
示例：
输入: [5, 4, 3, 2, 1]
输出: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
解释: 前三名运动员的成绩为前三高的，因此将会分别被授予 “金牌”，“银牌”和“铜牌” ("Gold Medal", "Silver Medal" and "Bronze Medal").
余下的两名运动员，我们只需要通过他们的成绩计算将其相对名次即可。 public class Solution {
// 排序法+二分查找排名
public String[] findRelativeRanks(int[] score) {
int n = score.length;
int[] copy = new int[n];
System.arraycopy(score, 0, copy, 0, n);
Arrays.sort(copy);
String[] res = new String[n];
for (int i = 0; i < n; i++) {
// 排名+当前排序数组中索引 = 数组长度
int rank = n - Arrays.binarySearch(copy, score[i]);
switch (rank) {
case 1:
res[i] = ("Gold Medal");
break;
case 2:
res[i] = ("Silver Medal");
break;
case 3:
res[i] = ("Bronze Medal");
break;
default:
// 不是奖牌排名,就放入排名
res[i] = String.valueOf(rank);
}
}
return res;
}
} 堆排序
- 堆排序、快速排序、归并排序是面试中最高频的3个面试
public class HeapSort {
public static void heapSort(int[] arr) {
if (arr.length < 2) {
return;
}
// 从小到大排序,是建立大根堆
// 从大到小排序,是建立小根堆
// 1.自底向上将原数组转换成最大堆，arr[0]是整个数组最大值
buildMaxHeap(arr);
// 2.依次交换数组首位（最大值）和数组末尾，然后对剩下的[0,n-1...)再进行堆化操作
for (int j = arr.length - 1; j >= 0; j--) {
// 交换大根堆顶部和数组末尾，数据末尾元素来到最终位置
swap(arr, 0, j);
// 依次对父节点为0位置,数组长度为i的元素进行堆化操作
heapify(arr, 0, j);
}
}
// 建立大根堆
private static void buildMaxHeap(int[] arr) {
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
heapify(arr, i, arr.length);
}
}
// 对 arr[0, n) 所形成的最大堆中，索引为parent的父节点元素，进行heapify操作
private static void heapify(int[] arr, int parent, int n) {
while (2 * parent + 1 < n) {
int left = 2 * parent + 1;
if (left + 1 < n && arr[left] < arr[left + 1]) {
left++;
}
// 大根堆,父最大,就停止遍历
if (arr[left] <= arr[parent]) {
break;
}
// 否则就最大值交换到父节点
swap(arr, parent, left);
// 父节点循环进行下去
parent = left;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} LC912 排序数组
排序算法是否掌握，可以用力扣912验证
class Solution {
// 排序算法是否掌握，用力扣912检验
public int[] sortArray(int[] arr) {
if (arr.length < 2) {
return arr;
}
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
heapify(arr, i, arr.length);
}
for (int j = arr.length - 1; j >= 0; j--) {
swap(arr, 0, j);
heapify(arr, 0, j);
}
return arr;
}
private static void heapify(int[] arr, int parent, int n) {
while (2 * parent + 1 < n) {
int left = 2 * parent + 1;
if (left + 1 < n && arr[left] < arr[left + 1]) {
left++;
}
// 大根堆,父最大,就停止遍历
if (arr[left] <= arr[parent]) {
break;
}
swap(arr, parent, left);
parent = left;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} LC215 找出第K个最大元素
题目：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
备注：高频面试题，解法很多，但面试官最希望的就是手写堆排序
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
public class Solution {
// 方法1:手写大根堆
public int findKthLargest1(int[] nums, int k) {
buildMaxHeap(nums);
// 数组首位交换k次,数组首位就是第K大的数
for (int i = nums.length - 1; i > nums.length - k; i--) {
swap(nums, 0, i);
heapify(nums, 0, i);
}
return nums[0];
}
// 建立大根堆
private static void buildMaxHeap(int[] arr) {
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
heapify(arr, i, arr.length);
}
}
// 对 arr[0, n) 所形成的最大堆中，索引为parent的父节点元素，进行heapify操作
private static void heapify(int[] arr, int parent, int n) {
while (2 * parent + 1 < n) {
int left = 2 * parent + 1;
if (left + 1 < n && arr[left] < arr[left + 1]) {
left++;
}
// 大根堆,父最大,就停止遍历
if (arr[left] <= arr[parent]) {
break;
}
// 否则就最大值交换到父节点
swap(arr, parent, left);
// 父节点循环进行下去
parent = left;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 方法2:使用PriorityQueue大根堆
public int findKthLargest2(int[] nums, int k) {
// 优先级队列默认是小根堆,拉姆达表达式改成大根堆
Queue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);
for (int num : nums) {
maxQueue.add(num);
}
// 第1大的数,第2大的数,第K大的数
// 移0次 移1次 移K-1次
for (int i = 0; i < k - 1; i++) {
maxQueue.remove();
}
return maxQueue.peek();
}
// 方法2:PriorityQueue小根堆
public int findKthLargest3(int[] nums, int k) {
// 因为第k大元素是k个元素中最小的,所以用小根堆
Queue<Integer> minQueue = new PriorityQueue<>();
// 先将数组前k个数放入小根堆
for (int i = 0; i < k; i++) {
minQueue.add(nums[i]);
}
// [1,2,3,4]中第2大的数是3,[1,2]的小根堆顶是2,比下一个数3小所以出队
// 因为排序后的后k个数虽然是这k个数中最小的,但确实非k个数中最大的,所以小根堆堆顶小了就要出队再入当前元素
for (int i = k; i < nums.length; i++) {
if (!minQueue.isEmpty() && minQueue.peek() < nums[i]) {
minQueue.remove();
minQueue.add(nums[i]);
}
}
// 此时小根堆堆顶,就是第K大的元素
return minQueue.peek();
}
// 法4:选择排序法
public int findKthLargest4(int[] nums, int k) {
// 外层循环k次
for (int i = 0; i < k; i++) {
// 找最大值就行
int maxIndex = i;
for (int j = i + 1; j < nums.length; j++) {
maxIndex = nums[maxIndex] < nums[j] ? j : maxIndex;
}
swap(nums, i, maxIndex);
}
// 第一次最大值下标=1-1=0;
// 第K次最大值下标=k-1
return nums[k - 1];
}
} 剑指Offer40 最小的第K个数
public class Solution {
// 最小的第K个数，用大根堆
public int[] getLeastNumbers(int[] arr, int k) {
// 优先级队列默认是小根堆,添加参数修改成大根堆
Queue<Integer> maxQueue = new PriorityQueue<>(11, (o1, o2) -> o2 - o1);
// 原数组前k个数放入大根堆
for (int i = 0; i < k; i++) {
maxQueue.add(arr[i]);
}
for (int i = k; i < arr.length; i++) {
// 大根堆堆顶比大，就移除
if (!maxQueue.isEmpty() && maxQueue.peek() > arr[i]) {
maxQueue.remove();
maxQueue.add(arr[i]);
}
}
// 依次移出大根堆，返回结果集数组中
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = maxQueue.remove();
}
return res;
}
} 快速排序
单路快排
public class QuickSort {
public static void quickSort(int[] arr) {
// random作为参数一致传递下去
Random random = new Random();
quickSort(arr, 0, arr.length - 1, random);
}
private static void quickSort(int[] arr, int l, int r, Random random) {
// 递归结束条件:显然只剩一个数时,递归结束
if (l >= r) {
return;
}
// 先划分区间
int p = partition(arr, 0, arr.length - 1, random);
// 左边递归排序
quickSort(arr, l, p - 1, random);
// 右边递归排序
quickSort(arr, p + 1, r, random);
}
private static int partition(int[] arr, int l, int r, Random random) {
int randomIndex = l + random.nextInt(r - l + 1);
swap(arr, l, randomIndex);
// j初始化为左边界
int j = l;
// 从左边界第一个数开始遍历
for (int i = l + 1; i < arr.length; i++) {
// j此时要求是指向<区域最后一个数
if (arr[i] < arr[l]) {
// 发现<arr[l],先移动j+1使得j指向>=arr[j]的第一个数,然后交换[i,j]位置的数
swap(arr, i, j++);
}
}
// 由于循环跳出j指向<区域最后一个数,与基准arr[l]交换
swap(arr, l, j);
// 交换后,j指向>=第一个数,返回该数=下标值
return j;
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
} 双路快排
public class QuickSort {
// 默写版
public static void quickSort(int[] arr) {
// random作为参数一致传递下去
Random random = new Random();
quickSort(arr, 0, arr.length - 1, random);
}
private static void quickSort(int[] arr, int l, int r, Random random) {
// 递归结束条件:显然只剩一个数时,递归结束
if (l >= r) {
return;
}
// 先划分区间
int p = partition(arr, l, r, random);
// 左边递归排序
quickSort(arr, l, p - 1, random);
// 右边递归排序
quickSort(arr, p + 1, r, random);
}
private static int partition(int[] arr, int l, int r, Random random) {
int randomIndex = l + random.nextInt(r - l + 1);
swap(arr, l, randomIndex);
// j初始化为左边界
int j = l;
// 从左边界第一个数开始遍历
for (int i = l + 1; i < arr.length; i++) {
// j此时要求是指向<区域最后一个数
if (arr[i] < arr[l]) {
// 发现<arr[l],先移动j+1使得j指向>=arr[j]的第一个数,然后交换[i,j]位置的数
swap(arr, i, j++);
}
}
// 由于循环跳出j指向<区域最后一个数,与基准arr[l]交换
swap(arr, l, j);
// 交换后,j指向>=第一个数,返回该数=下标值
return j;
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
} 三路快排
public class QuickSort2 {
public static void quickSort3way(int[] arr) {
if (arr.length < 2) {
return;
}
Random random = new Random();
quickSort3way(arr, 0, arr.length - 1, random);
}
private static void quickSort3way(int[] arr, int l, int r, Random random) {
if (l >= r) {
return;
}
// 分治:因为三路快排中间不用递归,避免partition返回值麻烦,所以partition和quickSort3ways写在一起
int randomIndex = l + random.nextInt(r - l + 1);
swap(arr, l, randomIndex);
// 核心：arr[l+1,lt]<v ; arr[lt+1,i-1]=v ; arr[gt,r]>v
// lt指向<的最后一个元素，i指针遍历，gt指向>的第一个元素
int lt = l, i = l + 1, gt = r + 1;
while (i < gt) {
if (arr[i] < arr[l]) {
lt++;
swap(arr, i, lt);
i++;
} else if (arr[i] > arr[l]) {
gt--;
swap(arr, i, gt);
// i所在位置从后往前发生了交换,导致nums[i]变新，需要重新比较,i无需++
} else {
i++;
}
}
// 交换l位置和小于第一个数
swap(arr, l, lt);
// 三路快排抛弃掉中间的部分，不再递归
quickSort3way(arr, l, lt - 1, random);
quickSort3way(arr, gt, r, random);
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
} LC169 最多的数字
题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3] 输出：3
示例 2：
输入：[2,2,1,1,1,2,2] 输出：2
public class Solution {
// 这道题可以用排序法，但是都没有摩尔投票法快
public int majorityElement(int[] nums) {
int cur = 0, count = 0;
for (int num : nums) {
// count为0,说明要更新遍历数字
if (count == 0) {
cur = num;
}
// 相同的数组就+1
if (cur == num) {
count++;
} else {
count--;
}
}
return cur;
}
} 归并排序
public class MergeSort {
public static void mergeSort(int[] arr) {
// 临时数组一开始就创建,传递到merge将arr复制给temp数组
int[] temp = Arrays.copyOf(arr, arr.length);
mergeSort(arr, 0, arr.length - 1, temp);
}
private static void mergeSort(int[] arr, int l, int r, int[] temp) {
if (l >= r) {
return;
}
// 先递归,划分区域
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid, temp);
mergeSort(arr, mid + 1, r, temp);
// 再归并,mid>前一个数才归并
if (arr[mid] > arr[mid + 1]) {
merge(arr, l, mid, r, temp);
}
}
private static void merge(int[] arr, int l, int mid, int r, int[] temp) {
System.arraycopy(arr, l, temp, l, r - l + 1);
int p = l, q = mid + 1;
for (int i = l; i <= r; i++) {
if (p > mid) {
arr[i] = temp[q++];
} else if (q > r) {
arr[i] = temp[p++];
} else if (temp[p] <= temp[q]) {
arr[i] = temp[p++];
} else {
arr[i] = temp[q++];
}
}
}
} LC88 合并两个有序数组
题目:给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6]
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1]
public class Solution {
// 面试最高频的一道题
// 方法1:双指针,从前往后遍历两个数组,需要辅助数组
public static void merge1(int[] nums1, int m, int[] nums2, int n) {
// temp存储每次排序好的数组
int[] temp = new int[m + n];
// p遍历nums1,q遍历nums2,i遍历temp
int p = 0, q = 0, i = 0;
while (p < m && q < n) {
temp[i++] = nums1[p] < nums2[q] ? nums1[p++] : nums2[q++];
}
while (p < m) {
temp[i++] = nums1[p++];
}
while (q < n) {
temp[i++] = nums2[q++];
}
// 将temp数组遍历回nums1
System.arraycopy(temp, 0, nums1, 0, m + n);
}
// 方法2:双指针,从后往前遍历两个数组,放最大,不需要辅助数组
public static void merge2(int[] nums1, int m, int[] nums2, int n) {
int p = m - 1, q = n - 1, i = m + n - 1;
// 从后往前找大的放入nums1中
while (p >= 0 && q >= 0) {
nums1[i--] = nums1[p] < nums2[q] ? nums2[q--] : nums1[p--];
}
// p<0上面遍历结束,此时q还没遍历到0,将nums2从[0,q+1)复制到nums1中
System.arraycopy(nums2, 0, nums1, 0, q + 1);
}
}
LC21 合并两个有序链表
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
递归的解法，常看动图，加深理解：力扣21递归解法查看
public class Solution {
// 迭代法:preHead.next返回结果，pre用于调整较小值
public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
// 设定一个哑结点,方便返回值
ListNode dummyNode = new ListNode(-1);
// cur指针指向每次比较的较小值结点
ListNode cur = dummyNode;
while (l1 != null && l2 != null) {
// 判断较小值,cur指向它
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
// 判断完后移cur
cur = cur.next;
}
// 循环结束,cur指向非空链表头部
cur.next = (l1 == null) ? l2 : l1;
return dummyNode.next;
}
// 递归法：判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果
// 因为l1、l2有序,所以递归最后一定是指向一个最短有序链表的,然后递归依次返回
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
// 递归结束条件:谁遍历到最后为null,返回另一个
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
// 递归判断，每一次都返回最小值结点进递归栈
if (l1.val < l2.val) {
l1.next = mergeTwoLists2(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists2(l1, l2.next);
return l2;
}
}
} 剑指51 数组中的逆序对问题
题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5
public class Solution {
// 将res作为参数传递,会出现各种问题,直接定义成员变量省事
private int res;
// 归并排序法，原理是利用nums[i]>nums[j],那么[i,mid]中都是逆序对个数
public int reversePairs(int[] nums) {
int[] temp = new int[nums.length];
res = 0;
mergeSort(nums, 0, nums.length - 1, temp);
return res;
}
private void mergeSort(int[] nums, int l, int r, int[] temp) {
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
mergeSort(nums, l, mid, temp);
mergeSort(nums, mid + 1, r, temp);
if (nums[mid] > nums[mid + 1]) {
merge(nums, l, mid, r, temp);
}
}
private void merge(int[] nums, int l, int mid, int r, int[] temp) {
System.arraycopy(nums, l, temp, l, r - l + 1);
int p = l, q = mid + 1;
for (int i = l; i <= r; i++) {
if (p > mid) {
nums[i] = temp[q++];
} else if (q > r) {
nums[i] = temp[p++];
} else if (temp[p] <= temp[q]) {
// <=区域不会形成逆序对,所以和归并排序过程一样
nums[i] = temp[p++];
} else {
// >说明必构成逆序对:[p,mid]与[mid+1,...]构成逆序对mid-p+1
res += mid - p + 1;
nums[i] = temp[q++];
}
}
}
} 非比较算法O(n)
计数排序
- 计数排序不基于元素的比较，只基于元素的出现次数，用R来表示一个元素的取值范围，利用count[R]记录每个元素出现次数，index[R+1]记录nums排好序后[index[i],index[i+1])的值为i
- 计数排序是稳定的,这是它最关键的一个性质
力扣75 颜色分类
题目:给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
示例 3：
输入：nums = [0] 输出：[0]
示例 4：
输入：nums = [1] 输出：[1]
public class Solution {
// 方法1:简单的记录出现元素次数，但对于理解计数排序法非常有帮助
public void sortColors1(int[] nums) {
// count数组记录0,1,2在nums中出现的次数
int[] count = new int[3];
for (int num : nums) {
if (num == 0) {
count[0]++;
} else if (num == 1) {
count[1]++;
} else {
count[2]++;
}
// 以上的写法可以等价:count[num]++;
}
// 注意下标之间的连接
for (int i = 0; i < count[0]; i++) {
nums[i] = 0;
}
for (int i = count[0]; i < count[1] + count[0]; i++) {
nums[i] = 1;
}
for (int i = count[1] + count[0]; i < count[2] + count[1] + count[0]; i++) {
nums[i] = 2;
}
}
// 方法2:计数排序法,这个方法有点像桶排序
public void sortColors2(int[] nums) {
// 1.定义元素取值范围:[0,3)
int R = 3;
int[] cnt = new int[R];
// 记录出现的次数
for (int num : nums) {
cnt[num]++;
}
// 2.index表示:nums排好序后[index[i],index[i+1])的值为i
// 因为0之前没有元素，单独用0位置存，所以是R+1个长度
int[] index = new int[R + 1];
// 只遍历到n-1的位置,因为末尾元素无cnt[R+1]对应
for (int i = 0; i < index.length - 1; i++) {
index[i + 1] = index[i] + cnt[i];
}
// 3.再次遍历到n-1,nums[index[i],index[i+1])=i
for (int i = 0; i < index.length - 1; i++) {
for (int j = index[i]; j < index[i + 1]; j++) {
nums[j] = i;
}
}
}
} 力扣1122 数组的相对顺序
题目：给你两个数组，arr1和 arr2，
- arr2 中的元素各不相同
- arr2 中的每个元素都出现在 arr1 中
- 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：数组长度不大于1k,每个元素取值返回不大于1k，就是提示你用计数排序法
1 <= arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 arr2 中的元素 arr2[i] 各不相同 arr2 中的每个元素 arr2[i] 都出现在 arr1 中
public class Solution {
// 计数排序法,取值范围为[0,1000]所以可以考虑使用计数排序法
public int[] relativeSortArray(int[] arr1, int[] arr2) {
// 1.找到arr1中最大值max,生成count[max+1]，count[0,max]记录arr1每个元素出现次数
int max = 0;
for (int num : arr1) {
max = Math.max(num, max);
}
// 2.只用计数排序中的count数组记录次数就行,不需要index数组
int[] count = new int[max + 1];
for (int num : arr1) {
count[num]++;
}
int[] res = new int[arr1.length];
int index = 0;
// 3.遍历arr2中元素,回count[num]=出现次数,放回res中
for (int num : arr2) {
for (int i = 0; i < count[num]; i++) {
res[index++] = num;
}
// 重点:用过的count[num]清零,说明
count[num] = 0;
}
// 4.遍历count,非0元素遍历个数回res中
for (int i = 0; i < count.length; i++) {
if (count[i] != 0) {
for (int j = 0; j < count[i]; j++) {
res[index++] = i;
}
}
}
return res;
}
} 基数排序
什么是数字的高位和低位？比如102，高位是1，低位是2，不要弄反
LSD算法
- 适用于等长字符串，通常不会用于数字的比较
- 如果用于比较数字，可以将数字转换为字符串数组，不等长的数字，前面高位补0再转换，并不会改变原排序位置
- 但是LSD不能用于非等长字符串，字符串补空格是行不通的，\0也是不行（某些语言\0是字符串结尾标识）
- 如果要比较非等长字符串，那就要用MSD算法
public class LSDSort {
// 参数提供一个len,提示调用者arr中元素等长的长度
public static void lSDSort(String[] arr, int len) {
// LSD算法,多用于字符串排序,这里参数直接使用字符串数组;并且LSD只适用于等长字符串
// LSD:Least significant digital,比如"ABC"中的“C”是低位,“A”是高位
for (String s : arr) {
if (s.length() != len) {
throw new IllegalArgumentException("All Strings' length must be the same.");
}
}
// Java中Char占1个字节=256位,取值范围0-255
int R = 256;
int[] cnt = new int[R];
int[] index = new int[R + 1];
// 辅助数组
String[] temp = new String[arr.length];
// LSD:从每个字符的末尾开始使用计数排序
for (int i = len - 1; i >= 0; i--) {
// 每次遍历开始,记录次数前清空cnt
Arrays.fill(cnt, 0);
// 记录次数
for (String s : arr) {
cnt[s.charAt(i)]++;
}
// 记录index数组
for (int j = 0; j < index.length - 1; j++) {
index[j + 1] = index[j] + cnt[j];
}
// 根据index,将各字符放回temp数组
for (String s : arr) {
// index[s.charAt(i)]=是s起始出现的坐标
temp[index[s.charAt(i)]] = s;
// 下一次出现的坐标+1
index[s.charAt(i)]++;
}
// 遍历temp赋值给原数组arr
for (int j = 0; j < arr.length; j++) {
arr[j] = temp[j];
}
}
}
public static void main(String[] args) {
String[] arr = {"a", "c", "d"};
LSDSort.lSDSort(arr, 1);
System.out.println(Arrays.toString(arr));
}
} MSD算法
- 边界处理：空（长度不够）对应的“字符值”最小,比如空比“A”还小
- 假设原先字符取值范围[0,R-1]R种可能，现在加上空值的可能，字符取值范围为[1,R]+[0]，规定[0]是空，长度为R+1
public class MSDSort {
public static void mSDSort(String[] arr) {
int N = arr.length;
String[] temp = new String[N];
mSDSort(arr, 0, N - 1, 0, temp);
}
/**
* @param arr 待排序数组arr
* @param left 对arr[i]待排序的最左边字符串
* @param right 对arr[i]待排序的最右边字符串
* @param r arr[i]的r位置,处理arr[left, right]
* @param temp 辅助数组一次性开辟出来
*/
private static void mSDSort(String[] arr, int left, int right, int r, String[] temp) {
// 递归结束条件
if (left >= right) {
return;
}
// 开始修改计数排序
// 字符取值范围
int R = 256;
// 由于有null值,index和cnt数组比LSD都要加一位
// 规定cnt[0]记录空值出现的次数
int[] cnt = new int[R + 1];
int[] index = new int[R + 2];
// 记录arr[i]中r位置字符出现的次数
for (int i = left; i <= right; i++) {
// 越界:r位置如果超过了字符的长度=遇到了空值,规定了cnt[0]记录空值,所以cnt[0]++
// 正常:cnt[arr[i].charAt(r) + 1]++
cnt[r >= arr[i].length() ? 0 : (arr[i].charAt(r) + 1)]++;
}
// 记录次数
for (int i = 0; i < cnt.length; i++) {
index[i + 1] = index[i] + cnt[i];
}
// 赋值给temp数组
for (int i = left; i <= right; i++) {
int p = r >= arr[i].length() ? 0 : (arr[i].charAt(r) + 1);
temp[left + index[p]] = arr[i];
index[p]++;
}
// temp赋值回原数组
for (int i = left; i <= right; i++) {
arr[i] = temp[i];
}
// 计数排序修改完成,开始递归,需要深刻理解
for (int i = 0; i < R; i++) {
mSDSort(arr, left + index[i], left + index[i + 1] - 1, r + 1, temp);
}
}
} 桶排序
public class BucketSort {
// 桶排序1:桶记录每个元素出现的次数
public static void bucketSort1(Integer[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 1.从所有数中找出最大值
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
// 2.生成max+1个元素的桶,使得桶[0,max]
int[] bucket = new int[max + 1];
// 3.遍历数组，每个元素出现的个数加入桶
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
// 4.遍历桶，将非0数据放回原数组
int index = 0;
for (int i = 0; i < bucket.length; i++) {
while (bucket[i]-- > 0) {
arr[index++] = i;
}
}
}
/**
* 桶排序2:用户指定每个桶的长度,另一种思维
*
* @param arr 待排序数组
* @param c 每个桶的长度
*/
public static void bucketSort2(int[] arr, int c) {
if (c <= 0) {
throw new IllegalArgumentException("c must be >0");
}
// 计算桶的数量
int B = arr.length / c + (arr.length % c > 0 ? 1 : 0);
List<Integer>[] buckets = new List[B];
for (int i = 0; i < B; i++) {
buckets[i] = new LinkedList<>();
}
// 找出数组中的最小值
int min = Integer.MAX_VALUE;
for (int num : arr) {
min = Math.min(min, num);
}
// 元素如桶：在几号桶? = (arr[i]-min)/桶数c
for (int num : arr) {
buckets[(num - min) / c].add(num);
}
// 使用库函数对每个桶中元素进行排序
for (int i = 0; i < buckets.length; i++) {
Collections.sort(buckets[i]);
}
// 将桶中元素，放回原数组
int index = 0;
for (int i = 0; i < buckets.length; i++) {
for (Integer num : buckets[i]) {
arr[index++] = num;
}
}
}
}
力扣164 最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10] 输出: 0 解释: 数组元素个数小于 2，因此返回 0。
public class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
// 1.统计数组长度,最大值,最小值
int N = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
// 如果最大值和最小值相同,最大间距为0,直接返回
if (min == max) {
return 0;
}
// 2.生成3个桶,每个桶长N+1
boolean[] hasNum = new boolean[N + 1];
int[] maxs = new int[N + 1];
int[] mins = new int[N + 1];
// 3.最大值桶只放区间最大值，最小值桶只放区间最小值
// bid是桶id,记录放入桶的编号
int bid = 0;
// 有几个数就要遍历几次=遍历N次
for (int i = 0; i < N; i++) {
// 算出每个元素放入桶中的id
bid = getBucketId(nums[i], N, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
// 4.排序后，相邻元素的最大差值=(当前非空桶最小值-上一个非空桶最大值)中的最大值
int maxGap = 0;
int lastMax = maxs[0];
// 从第2个桶开始统计最大差值
for (int i = 1; i <= N; i++) {
if (hasNum[i]) {
// 相邻元素的最大差值=(当前非空桶最小值-上一个非空桶最大值)中的最大值
maxGap = Math.max(maxGap, mins[i] - lastMax);
// 更新上一个非空桶的最大值
lastMax = maxs[i];
}
}
return maxGap;
}
// 计算num放入哪个桶:(arr[i]-min)/桶长,桶长=(max-min)/len
// 注意:数据类型全部用long,因为有乘法int会溢出
private int getBucketId(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
} LC561 数组拆分I
题目：给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
示例 1：
输入：nums = [1,4,3,2] 输出：4 解释：所有可能的分法（忽略元素顺序）为： 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 所以最大总和为 4
示例 2：
输入：nums = [6,2,6,5,1,2] 输出：9 解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
public class Solution {
// 力扣561:2n长度数组拆分n对(a,b)形式，找出每队最小值之和的最大和
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int res = 0;
// 排序后,间隔为2的每位数之和=n对最小值之和的最大和
for (int i = 0; i < nums.length; i += 2) {
res += nums[i];
}
return res;
}
} 排序算法总结
情绪（稳定性）不稳定：快（快速排序）些（希尔排序）选（选择排序）堆（堆排序）
| 排序名称 | 时间复杂度 | 空间复杂度 | 稳定性 | 备注 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2)，完全有序变成O(n) | O(1) | 稳定 | 力扣283移动数字0 |
| 选择排序 | O(n^2) | O(1) | 不稳定 | 运行时间和输入无关；数据移动是最少的 |
| 插入排序 | O(n^2)，完全有序变成O(n) | O(1) | 稳定 | 排序时间取决于初始值（使用交换方式） |
| 希尔排序 | O(nlogn)-O(n^2) | O(1) | 不稳定 | 分组思想 |
| 堆排序 | O(nlogn) | O(1) | 不稳定 | 实现优先队列 |
| 快速排序 | O(nlogn)，含有相同元素数组，三路快排O(n) | O(1) | 不稳定 | 求解topK等问题 |
| 归并排序 | O(nlogn)，完全有序变成O(n) | O(n) | 稳定 | 求解逆序对、小和、染色等问题 |
京公网安备 11010502036488号