LeetCode刷题：排序和二分查找

关于排序和二分查找的几个必知必会的代码实现

排序

• 实现归并排序、快速排序、插入排序、冒泡排序、选择排序

• 编程实现 $O(n)$ 时间复杂度内找到一组数据的第 K 大元素

二分查找

• 实现一个有序数组的二分查找算法

• 实现模糊二分查找算法（比如大于等于给定值的第一个元素）

排序题目

Relative Sort Array(数组的相对排序)

题目：

给你两个数组，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]

提示：

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2 中的元素 arr2[i] 各不相同
• arr2 中的每个元素 arr2[i] 都出现在 arr1 中

思路：

先对 arr1 进行排序，然后按照 arr2 的顺序放置 arr1 的元素，最后剩下的元素放在末尾即可。

代码：

public int[] relativeSortArray(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length];
    Arrays.sort(arr1);
    int k = 0;
    for (int i = 0; i < arr2.length; i++) {
        for (int j = 0; j < arr1.length; j++) {
            if ((arr1[j] != -1) && (arr1[j] == arr2[i])) {
                result[k ++] = arr1[j];
                arr1[j] = -1;
            }
        }
    }
    for (int i = 0; i < arr1.length; i++) {
        if (arr1[i] != -1) {
            result[k ++] = arr1[i];
        }
    }
    return result;
}

二分查找题目

Sqrt(x) （x 的平方根）

题目：

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

思路：

这里提供了两种方法，分别是二分法和牛顿法，点击查看
二分查找法应用于搜索平方根的思想很简单，其实就是“猜”，但是是有策略的“猜”，用“排除法”在有限的区间里，一次排除一半的区间元素，最后只剩下一个数，这个数就是题目要求的向下取整的平方根整数。

牛顿法最初提出的时候，是用于求解方程的根，它的基本思想是“以直代曲”，在迭代中搜索得到方程的近似解。

代码：

public int mySqrt(int x) {
    long left = 0;
    long right = Integer.MAX_VALUE;
    while (left < right) {
        // 这种取中位数的方法又快又好
        // 注意：这里得用无符号右移
        long mid = (left + right + 1) >>> 1;
        long square = mid * mid;
        if (square > x) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    return (int) left;
}