title: 每日一練（7）：旋轉數組的最小數字

categories:[劍指offer]

tags:[每日一練]

date: 2022/01/20

每日一練（7）：旋轉數組的最小數字

把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。

給你一個可能存在 重復 元素值的數組 numbers ，它原來是一個升序排列的數組，并按上述情形進行了一次旋轉。請返回旋轉數組的最小元素。例如，數組

[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

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

方法一：二分查找

算法流程：

• 1.初始化： 聲明 i, j 雙指針分別指向 nums 數組左右兩端；

• 2.循環(huán)二分： 設 m = (i + j) / 2 為每次二分的中點（ "/" 代表向下取整除法，因此恒有 i ≤ m < j ），

  可分為以下三種情況：

  • 1.當 nums[m] > nums[j] 時： m 一定在 左排序數組 中，即旋轉點 x 一定在 [m + 1, j] 閉區(qū)間內，因此執(zhí)行 i=m+1；
  • 2.當 nums[m] < nums[j] 時： m 一定在 右排序數組 中，即旋轉點 x 一定在 [i, m] 閉區(qū)間內，因此執(zhí)行 j = m；
  • 3.當 nums[m] = nums[j]時： 無法判斷 m 在哪個排序數組中，即無法判斷旋轉點 x 在 [i, m] 還是 [m + 1, j] 區(qū)間中。解決方案： 執(zhí)行 j = j - 1 縮小判斷范圍，分析見下文。

• 3.返回值： 當 i=j 時跳出二分循環(huán)，并返回 旋轉點的值 nums[i] 即可。

復雜度：

• 時間復雜度 O(log_2 N) ： 在特例情況下（例如 [1, 1, 1, 1] ），會退化到 O(N)。
• 空間復雜度 O(1) ： i , j , m 變量使用常數大小的額外空間。

int minArray(vector<int>& numbers) {
    int i = 0, j = numbers.size() - 1;
    while (i < j) {
        int m = (i + j) / 2;
        if (numbers[m] > numbers[j]) { //[m + 1, j] 閉區(qū)間內
            i = m + 1;
        } else if (numbers[m] < numbers[j]) { //[i, m] 閉區(qū)間內
            j = m;
        } else {//縮小判斷范圍
            j--; 
        }
    }
    return numbers[i];
}

方法二：線性查找

實際上，當出現 nums[m] = nums[j] 時，一定有區(qū)間 [i, m] 內所有元素相等 或 區(qū)間 [m, j] 內所有元素相等（或兩者皆滿足）。對于尋找此類數組的最小值問題，可直接放棄二分查找，而使用線性查找替代。

int minArray(vector<int>& numbers) {
    int i = 0, j = numbers.size() - 1;
    while (i < j) {
        int m = (i + j) / 2;
        if (numbers[m] > numbers[j]) {//[m + 1, j] 閉區(qū)間內
            i = m + 1;
        } else if (numbers[m] < numbers[j]) {//[i, m] 閉區(qū)間內
            j = m;
        } else {
            int x = i;
            for(int k = i + 1; k < j; k++) {
                if(numbers[k] < numbers[x]) {
                    x = k;
                }
            }
            return numbers[x];
        }
    }
    return numbers[i];
}