面试题:Java 实现查找旋转数组的最小数字

Java 实现查找旋转数组的最小数字

什么是旋转数组

旋转数组指的是按照某个位置将一个有序数组分成左右两个部分，并交换这两个部分的位置而形成的新的数组。例如，原始数组为 [1, 2, 3, 4, 5]， 将其按照位置 3 进行旋转，得到的旋转数组为 [4, 5, 1, 2, 3]。

如何查找旋转数组的最小数字

旋转数组中的最小数字就是数组中最小的数。由于数组是旋转过的，因此我们需要对数组进行特殊处理来查找最小数字。有以下两种方法：

方法一：暴力法

遍历旋转数组，找到最小数字，时间复杂度为O(n)。如下所示：

public static int findMinNumber(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int min = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    return min;
}

方法二：二分查找

二分查找是一种更加高效的方法，时间复杂度为O(log n)。具体思路如下：

旋转数组可以分成两个有序的子数组，而且左边的子数组所有元素都大于右边子数组中的元素。我们可以利用这个特点，使用二分查找的思路进行查找。

• 首先取中间位置的值 mid
• 如果 mid 比 right 大，说明 mid 在左边子数组中，令 left = mid + 1
• 如果 mid 比 right 小，说明 mid 在右边子数组中，令 right = mid
• 如果 mid 和 right 相等，说明无法判断 mid 在左边还是右边，令 right--

具体实现代码如下：

public static int findMinNumber(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0, right = nums.length - 1, mid;
    while (left < right) {
        mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            right--;
        }
    }
    return nums[left];
}

示例

1. 对于旋转数组 [3,4,5,1,2]，最小数字为 1，使用方法二的二分查找，得到的结果为 1。

2. 对于旋转数组 [4,4,4,4,4]，最小数字为 4，使用方法二的二分查找，得到的结果为 4。

以上两个示例证明了方法二的正确性，同时也展示了方法二对于特殊情况的处理方式，如旋转数组中有相同数字。