剑指 Offer 11. 旋转数组的最小数字

题目

1
2
3
4
5
6
7
8
9
10
11
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  

示例 1：

输入：[3,4,5,1,2]
输出：1
示例 2：

输入：[2,2,2,0,1]
输出：0

暴力求解

毫无算法可言

1
2
3
4
5
6
7
8
9
public int minArray(int[] numbers) {
    int min = numbers[0];
    for (int i = 1; i < numbers.length; i++) {
        if (min > numbers[i]){
            min = numbers[i];
        }
    }
    return min;
}

思路

二分求解

什么？二分只能用于有序？那我是不是要把数组排列为有序？

二分不仅仅是只能用于有序，难道部分有序不行吗？

因为 这个不是整体有序，所以我们在使用二分法的时候要注意临界值，即旋转点的位置。

重要：题目：原来的数组是整体有序递增的，这个数组一定是经过翻转的

所以原来的数组在经过翻转后，一定是分为两端递增，而且中间（最左或最右的一个）一定有一个最低点

fig2

fig4

先拿到两头的两个数据：numbers[i]，numbers[j]

1
int i = 0, j = numbers.length -1;

中间的数据：numbers[m]

1
int m = (i+j)/2;

主要为三种情况：

  1. numbers[m] > numbers[j]

    这个时候最低点的那个数据，一定在m的右侧。

    因为一个递增数组，只翻转了一次，那么比numbers[j]大的数据一定在最低点左侧，比numbers[小]大的数据一定在最低点右侧。可以自己画一个图然后截取翻转一下

    1
    i = m + 1;

  2. numbers[m] < numbers[j]

    这个时候最低点的那个数据，一定在m的左侧。

1
j = m

  1. numbers[m] == numbers[j]

    如果两个数想等，说明这个序列存在重复的数据，这个时候我们无法判断，这个最低点的位置，所以需要向左或者向右移动再次比较，但是因为我们最开始就是拿的两头的值进行的比较，所以我们只能m和j左侧的数据比较

    1
    j--

因为i和j一直在变化，所以最后循环跳出的条件就是i==j，所以最后返回numbers[i]，numbers[j]都行

二分法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static class Solution2 {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) {
                i = m + 1;
            } else if (numbers[m] < numbers[j]) {
                j = m;
            } else {
                j--;
            }
        }
        return numbers[i];
    }
}

时间复杂度 :O(log 2N) ： 在特例情况下（例如 [1, 1, 1, 1])，会退化到 O(N)。
空间复杂度 :O(1) ： i , j , m 变量使用常数大小的额外空间。

二分法优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int minArray(int[] numbers) {
            int i = 0, j = numbers.length - 1;
            while (i < j) {
            //主要是在这一步进行了优化，防止溢出
                int m = i+  (j - i) / 2;
                if (numbers[m] > numbers[j]) {
                    i = m + 1;
                } else if (numbers[m] < numbers[j]) {
                    j = m;
                } else {
                    j--;
                }
            }
            return numbers[i];
        }

追加

输入一个递减排序的数组的一个旋转，求最大值（最小值）

求最大值

image-20210906104851529

同样的思路：

  1. numbers[m] > numbers[j]

    那么这个最大值一定在m的右侧

    1
    j = m

  2. numbers[m] < numbers[j]

    那么这个最大值一定在m的左侧

1
i = m + 1;
  1. numbers[m] == numbers[j]
1
j--

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = i+  (j - i) / 2;
            if (numbers[m] > numbers[j]) {
                j = m;
            } else if (numbers[m] < numbers[j]) {
                i = m +1;
            } else {
                j--;
            }
        }
        return numbers[i];
    }
}

求最小值

求最小值就是求最大值得一个变形，最小值一定在最大值得左侧

而且在求的得最大值，如果有重复值，一定是最左的那一个，因为如果numbers[m] == numbers[j]相等，那么j会一直向左移动，伴随着m也会向左移动，知道j和i相当，获取遇到了numbers[m] != numbers[j]，这个过程都是在想左移动

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = i+  (j - i) / 2;
            if (numbers[m] > numbers[j]) {
                j = m;
            } else if (numbers[m] < numbers[j]) {
                i = m +1;
            } else {
                j--;
            }
        }
        return numbers[i-1];
    }
}

验证最值

这次我们没有leetcode的在线验证工具，因为这道题是自己临时想到的，这个时候我们可以使用对数器来检验我们的设计的算法的正确性

绝对正确的答案

1
2
3
4
5
6
7
8
9
10
11
private static class Solution3 {
    public int minArray(int[] numbers) {
        int max = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if (max <  numbers[i]) {
                max = numbers[i];
            }
        }
        return max;
    }
}

或者使用Arrays的api

1
2
3
4
5
private static class Solution3 {
    public int minArray(int[] numbers) {
        return Arrays.stream(numbers).max().getAsInt();
    }
}

对数器设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class ArryRotateMinPlus {
    public static void main(String[] args) {
        Solution solution = new Solution();
        for (int i = 0; i < 1000; i++) {
            int[] numbers = getNumbers(100);
            int[] numbers1 = Arrays.copyOf(numbers, numbers.length);
            rotate(numbers, (int) (Math.random() * numbers.length));
            if (getmax(numbers) != solution.minArray(numbers)) {
                System.out.println("算法错误啦!你的答案是" + solution.minArray(numbers) + "正确答案是：" + getmax(numbers));
                System.out.println("错误的原始递减数组是：" + Arrays.toString(numbers1));
                System.out.println("错误的翻转递减数组是：" + Arrays.toString(numbers));
                return;
            }
        }
        System.out.println("恭喜你！吕小医，你的算法正确啦！");


    }

    /**
     * 递减数组求最大值
     */
    private static class Solution {
        public int minArray(int[] numbers) {
            int i = 0, j = numbers.length - 1;
            while (i < j) {
                int m = i + (j - i) / 2;
                if (numbers[m] > numbers[j]) {
                    j = m;
                } else if (numbers[m] < numbers[j]) {
                    i = m + 1;
                } else {
                    j--;
                }
            }
            return numbers[i];
        }
    }

    /**
     * 递减数组求最小值
     */
    private static class Solution2 {
        public int minArray(int[] numbers) {
            int i = 0, j = numbers.length - 1;
            while (i < j) {
                int m = i + (j - i) / 2;
                if (numbers[m] > numbers[j]) {
                    j = m;
                } else if (numbers[m] < numbers[j]) {
                    i = m + 1;
                } else {
                    j--;
                }
            }
            return numbers[i - 1];
        }
    }

    //绝对正确的算法
    public static int getmax(int[] numbers) {
        return Arrays.stream(numbers).max().getAsInt();
    }

    // 获取一个递减的数组
    public static int[] getNumbers(int count) {
        int[] numbers = new int[count];
        for (int i = 0; i < count; i++) {
            numbers[i] = (int) (Math.random() * 100);
        }
        // 对数组进行从小到大排序
        Arrays.sort(numbers);
        reserve(numbers, 0, numbers.length - 1);
        return numbers;
    }

    //获得递减的反战数组，k是反转的长度
    private static void rotate(int[] nums, int k) {
        int length = nums.length;
        if (length == 1) {
            return;
        }
        k = k % length;
        reserve(nums, 0, length - 1);
        reserve(nums, 0, k - 1);
        reserve(nums, k, length - 1);
    }

    private static void reserve(int[] nums, Integer start, Integer end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

博客首先发布于：

https://lvxiaoyi.top/