【剑指Offer】排序

2024-03-13 14:44:45

文章目录

励志

Money is not life’s report card.
金钱不能用来衡量人生精彩与否。

常见算法

【剑指Offer】排序
下图所示，为在 「随机乱序」、「接近有序」、「完全倒序」、「少数独特」四类输入数据下，各常见排序算法的排序过程。

【剑指Offer】排序

【剑指Offer】排序

【剑指Offer】排序

【剑指Offer】排序

【剑指Offer】排序

【剑指Offer】排序

排序算法主要可根据 稳定性 、就地性 、自适应性 分类。

  • 具有稳定性，即相等元素的相对位置不变化；
  • 具有就地性，即不使用额外的辅助空间；
  • 具有自适应性，即时间复杂度受元素分布影响；

冒泡排序：

AC模板：

void bubbleSort(int[] nums) {
	int N = nums.length;
	for (int i = 0; i < N - 1; i++) {  
		for (int j = 0; j < N - i - 1; j++) { 
			if (nums[j] > nums[j + 1]) {
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
			}
		}
	}
}
  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)

优化版的冒泡排序：

void bubbleSort(int[] nums) {
	int N = nums.length;
	for (int i = 0; i < N - 1; i++) {
		boolean flag = false; // 初始化标志位
		for (int j = 0; j < N - i - 1; j++) {
			if (nums[j] > nums[j + 1]) {
				int tmp = nums[j];
				nums[j] = nums[j + 1];
				nums[j + 1] = tmp;
				flag = true;  // 记录交换元素
			}
		}
		if (!flag) break;     // 内循环未交换任何元素，则跳出
	}
}

若在某轮「内循环」中未执行任何交换操作，则说明数组已经完成排序

快速排序:

算法思想：哨兵划分 和 递归

哨兵划分：
以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

递归：
对 左子数组 和 右子数组 分别递归执行 哨兵划分

AC模板：

void quickSort(int[] nums, int l, int r) {
    // 子数组长度为 1 时终止递归
    if (l >= r) return;
    // 哨兵划分操作
    int i = partition(nums, l, r);
    // 递归左（右）子数组执行哨兵划分
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

int partition(int[] nums, int l, int r) {
    // 以 nums[l] 作为基准数
    int i = l, j = r;
    while (i < j) {
    // 因为我们将最左边的数字作为基准
    // 所以先j--，然后i++（先移动j，后移动i）
        while (i < j && nums[j] >= nums[l]) j--;
        while (i < j && nums[i] <= nums[l]) i++;
        swap(nums, i, j);
    }
    swap(nums, i, l);
    return i;
}

void swap(int[] nums, int i, int j) {
    // 交换 nums[i] 和 nums[j]
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

快速排序的常见优化手段有「Tail Call」和「随机基准数」两种。

Tail Call:
控制递归深度，每次递归短数组

void quickSort(int[] nums, int l, int r) {
    // 子数组长度为 1 时终止递归
    while (l < r) {
        // 哨兵划分操作
        int i = partition(nums, l, r);
        // 仅递归至较短子数组，控制递归深度
        if (i - l < r - i) {
            quickSort(nums, l, i - 1);
            l = i + 1;
        } else {
            quickSort(nums, i + 1, r);
            r = i - 1;
        }
    }
}

随机基准数：
每轮在子数组中找一个随机基准数

int partition(int[] nums, int l, int r) {
    // 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
    int ra = (int)(l + Math.random() * (r - l + 1));
    swap(nums, l, ra);
    // 以 nums[l] 作为基准数
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= nums[l]) j--;
        while (i < j && nums[i] <= nums[l]) i++;
        swap(nums, i, j);
    }
    swap(nums, i, l);
    return i;
}

归并排序：

算法思想： 分而治之

分：不断将数组从 中点位置 划分开

治：将 左右两个较短排序数组 合并为 一个较长排序数组

AC模板：

void mergeSort(int[] nums, int l, int r) {
    // 终止条件
    if (l >= r) return;
    // 递归划分
    int m = (l + r) / 2;
    mergeSort(nums, l, m);
    mergeSort(nums, m + 1, r);
    // 合并子数组
    int[] tmp = new int[r - l + 1]; // 暂存需合并区间元素
    for (int k = l; k <= r; k++)
        tmp[k - l] = nums[k];
    int i = 0, j = m - l + 1;       // 两指针分别指向左/右子数组的首个元素
    for (int k = l; k <= r; k++) {  // 遍历合并左/右子数组
        if (i == m - l + 1)
            nums[k] = tmp[j++];
        else if (j == r - l + 1 || tmp[i] <= tmp[j])
            nums[k] = tmp[i++];
        else {
            nums[k] = tmp[j++];
        }
    }
}

一、剑指 Offer 40. 最小的 k 个数

题：

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

解：

解题思路：快速排序
AC代码：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int len = arr.length;
        if(k >= len) return arr;
        return quick_sort(arr, k, 0, len - 1);
    }
    int[] quick_sort(int[] nums, int k, int left, int right){
        int i = left, j = right;
        while(i < j){
            while(i < j && nums[j] >= nums[left]) j--;
            while(i < j && nums[i] <= nums[left]) i++;          
            if(i < j) swap(nums, i, j);
        }
        swap(nums, left, i);
        if(k < i) return quick_sort(nums, k, left, i-1);
        else if(k > i) return quick_sort(nums, k, i+1, right);
        return Arrays.copyOf(nums, k);
    }
    void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

二、剑指 Offer 41. 数据流中的中位数

题：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1：

输入
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

最多会对 addNum、findMedian 进行 50000 次调用。

解：

解题思路： 大顶堆 + 小顶堆
AC代码：

class MedianFinder {

    Queue<Integer> A, B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>(); // 大顶堆
        B = new PriorityQueue<>((x, y) -> (y - x)); // 小顶堆
    }
    
    public void addNum(int num) {
        if(A.size() != B.size()){ // A少B多
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

三、剑指 Offer 45. 把数组排成最小的数

题：

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

0 < nums.length <= 100

说明:

  • 输出结果可能非常大，所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

解：

解题思路： 快速排序
AC代码：

class Solution {
    public String minNumber(int[] nums) {
        int len = nums.length;
        String[] strs = new String[len]; // 数组变字符串数组
        for(int i = 0; i < len; i++) strs[i] = String.valueOf(nums[i]); 
        quickSort(strs, 0, len-1);
        StringBuilder res = new StringBuilder(); // 字符串数组转字符串
        for(String str : strs) res.append(str);
        return res.toString();
    }
    void quickSort(String[] strs, int l, int r){
        if(l >= r) return; 
        int i = l, j = r;
        while(i < j){
            while(i < j && (strs[l] + strs[j]).compareTo(strs[j] + strs[l]) <= 0) j--; // l+j < j+l
            while(i < j && (strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0) i++; // i+l < l+i
            if(i < j) swap(strs, i, j);
        }
        swap(strs, i, l);
        quickSort(strs, l, i-1);
        quickSort(strs, i+1, r);
    }
    void swap(String[] strs, int i, int j){
        String temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }
}

另解：内置函数

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
}

四、剑指 Offer 61. 扑克牌中的顺子

题：

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：

数组长度为 5 

数组的数取值为 [0, 13] .

解：

解题思路：集合Set + 遍历
AC代码：

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums){
            if(num == 0) continue; // 跳过大小王
            max = Math.max(num, max);
            min = Math.min(num, min);
            if(repeat.contains(num)) return false; // 顺子不能有一样的牌
            repeat.add(num);
        }
        return max -min < 5;
    }
}
  • 时间复杂度 O(1) ： 本题中给定牌数量 N≡5 ；遍历数组使用 O(N) = O(5) = O(1)时间。
  • 空间复杂度 O(1) ： 用于判重的辅助 Set 使用 O(N) = O(1) 额外空间。

解题思路：排序+遍历
AC代码：

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0; // 大小王的数量, 顺子起始下标
        Arrays.sort(nums);
        for(int i = 0; i < 4; i++){
            if(nums[i] == 0){ // 碰到大小王
               joker++; 
               continue; 
            }
            if(nums[i] == nums[i+1]) return false; // 存在重复元素
        }
        return nums[4] - nums[joker] < 5;
    }
}
上一篇：14.最长公共前缀


下一篇：最长公共前缀