本文最后更新于:10 个月前

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

排序

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

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

二分查找

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

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

排序题目

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

题目:

给你两个数组,arr1arr2

  • 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;
}


欢迎关注我的公众号😘