题目描述（困难难度）

153 题 升级版，依旧是旋转过的数组，一个排序好的数组，把前边的若干的个数，一起移动到末尾，找出最小的数字。只不过这道题中的数字可能有重复的。

思路分析

想一下 153 题 我们怎么做的。

mid 和 end 比较。

mid < end：最小值在左半部分。

mid > end：最小值在右半部分。

所以我们只需要把 mid 和 end 比较，mid < end 丢弃右半部分（更新 end = mid），mid > end 丢弃左半部分（更新 start = mid + 1）。直到 end 等于 start 时候结束就可以了。

之前没有重复的数字，所以 mid 要么大于 end ，要么小于 end。这里的话，就需要考虑如果 mid == end 的话，我们该怎么做。代码框架也就出来了。

public int findMin(int[] nums) {
    int start = 0;
    int end = nums.length - 1;
    while (start < end) {
        int mid = (start + end) >>> 1;
        if (nums[mid] > nums[end]) {
            start = mid + 1;
        } else if (nums[mid] < nums[end]) {
            end = mid;
        } else {
            //添加代码
        }
    }
    return nums[start];
}

可以想几个例子考虑下。

3  3  1  2  3  3  3  3  3
            ^           ^
           mid         end 
上边的情况， mid == end，此时最小值在 mid 左边
3  3  3  3  3  2  3
         ^        ^
        mid      end 
上边的情况， mid == end，此时最小值在 mid 右边
2  3  3  1  1  1  1  1  1
            ^           ^
           mid         end 
上边的情况， mid == end，此时最小值在 mid 左边

当相等的时候，最小值可能在左边，也可能在右边，问题的关键就是去解决这个问题。

想法一

我想到的一种解决方案是如果遇到了相等的情况，将 mid 指针不停的向左滑动，直到当前的值不再等于 end。然后就会有三种情况。

• 情况一，移动结束的值小于了 end，此时最小值一定在 mid 的左边

  3  3  1  2  3  3  3  3  3
              ^           ^
             mid         end

• 情况二，移动结束的值大于了 end，此时最小值一定是结束位置的后一个值

  2  3  3  1  1  1  1  1  1
              ^           ^
             mid         end

• 情况三，移动到头后依旧是等于 end，此时最小值一定在 mid 的右边

  3  3  3  3  3  2  3
           ^        ^
          mid      end

大于小于等于也只有上边的三种情况了，所以代码也就出来了。

public int findMin(int[] nums) {
    int start = 0;
    int end = nums.length - 1;
    while (start < end) {
        int mid = (start + end) >>> 1;
        if (nums[mid] > nums[end]) {
            start = mid + 1;
        } else if (nums[mid] < nums[end]) {
            end = mid;
        } else {
            int temp = mid;
            //不停前移
            while (temp >= 0) {
                if (nums[temp] == nums[end]) {
                    temp--;
                //情况一
                } else if (nums[temp] < nums[end]) {
                    end = mid;
                    break;
                //情况二
                } else {
                    return nums[temp + 1];
                }
            }
            //情况三
            if (temp == -1) {
                start = mid + 1;
            }
        }
    }
    return nums[start];
}

想法二

参考 这里 ，非常简洁优雅。

主要思想就是把问题转换回 153 题 ，同样也是解决相等的时候怎么办。

只做一件事，end--。因为 mid 和 end 相等，所以我们直接把 end 抛弃一定不会影响结果的。

public int findMin(int[] nums) {
    int start = 0;
    int end = nums.length - 1;
    while (start < end) {
        int mid = (start + end) >>> 1;
        if (nums[mid] > nums[end]) {
            start = mid + 1;
        } else if (nums[mid] < nums[end]) {
            end = mid;
        } else {
           end--;
        }
    }
    return nums[start];
}

想法三

参考 这里 。

首先根据题目的意思，数组是被分成了两段。

当有重复数字的时候，之所以麻烦，就是因为有一个重复数字可能会被切割在两段里，比如下边的例子。

3  3  1  2  3  3  3  3  3
            ^           ^
           mid         end 
分成了 3 3 和 1 2 3 3 3 3 两段，3 同时处于两段
3  3  3  3  3  2  3
         ^        ^
        mid      end 
分成了 3 3 3 3 和 2 3 两段，3 同时处于两段

而如果所有重复的数字只处于一段里，其实并不复杂，比如下边的例子

1  2  3  3  3  3
      ^        ^
     mid      end
只有一段 1 2 3 3 3 3
7  7  6  6  6
      ^     ^
     mid   end
分成了 7 7 和 6 6 6 两段，没有数字处于两段里

对于上边的情况，其实我们可以确定，当 mid 和 end 相等的时候，最小值一定在 start 到 mid 之间。也就是和 mid < end 的情况一致的。

所以我们可以做一个预处理，保证所有重复数字不在两段里出现即可，再简单化，也就是保证切割的位置不要是重复数字。也就是比较 start 和 end 是否相同，相同的话 end-- 即可。

while (nums[end] == nums[start] && end > start) {
    end--;
}

最后只要把 153 题 的代码拿过来即可。

public int findMin(int[] nums) {
    int start = 0;
    int end = nums.length - 1;
    while (nums[end] == nums[start] && end > start) {
        end--;
    }
    while (start < end) {
        int mid = (start + end) >>> 1;
        if (nums[mid] > nums[end]) {
            start = mid + 1;
        } else{
            end = mid;
        }
    }
    return nums[start];
}

总

思路一主要是对新出现的情况进行细分来解决问题，思路二和思路三是把问题向原先的问题靠拢，从而尽可能少的变动了代码。不过这道题由于一些情况很特殊，所以虽然用了二分，最坏时间复杂度也降到了 O(n)，不再是 log 级的。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情