剑指offer_11

Posted on | In ,

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 剑指 Offer 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
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
       * 解题：  二分查找
       *
       * 这里把前部分数组叫做递增数组，把后部分数组叫做旋转数组。
       *
       * 由于不是一个严格递增的数组所以需要对原来的二分查找有所修改。
       * 当然开始也是求出位置为一半的值：mid
       * number[mid]和 number[left] 与 number[right] 相比较。考虑：
       *      情况一：number[mid] 小于 number[left] 说明mid在被旋转的数组区域，
       *          那么mid之后的就可以被舍弃了，最小值不在这里，但mid不能被舍弃，因为它还有可能是最小值。right = mid
       *      情况二：number[mid] 大于等于 number[left] 说明mid在递增的前一部分区间。
       *          那么mid之前的被舍弃，最小值不在这部分，mid也可以被舍弃。 left = mid + 1
       *      情况三：被舍弃后可能会出现完全递增的情况，即递增数组部分完全被舍弃了。
       *          此时也是需要判断  number[left] 与 number[right] ；
       *          如果 number[left] 小于 number[right]： 直接返回 number[left]
       *      情况四：一轮舍弃之后还可能出现 number[right] 是最小值的情况，即之前的都递增，到 right位置掉了下来。
       *            这种情况可以在下一轮自动找出来。
       *              比如[1,2,0] left会编程0位置上，那么left==right跳出循环。
       *              但是如果是 [1,2,3,0] 那么mid是2的位置属于情况二,left变成3的位置，数组成了[3,0]。
       *              此时再求mid是3的位置，number[mid] 等于 number[left]    属于情况二，left变为0的位置跳出循环。
       * 所以二分查找的重点在于左右游标的一个只管mid另一个要舍掉更多。
       *
       * 如果思考一个完全递增数组的二分查找的话。也可以分析出这样的多种情况；
       * 求出位置为一半的值：mid
       * number[mid]和 要查找的 target 相比较。考虑：
       *      情况一：number[mid] 小于 target；那么肯定 target 在 mid之后；
       *      情况二：number[mid] 大于 target；那么 target在 mid 之前。
       *      情况三：number[mid] 等于 target；那么 target就在 mid 位置，直接返回mid
       *      情况一和情况二下，这个舍弃 mid，那边都可以选择不要，还是要考虑最后怎么跳出循环：
       *           例如数组：[1,2,3] 查找 3 ；mid找到是2的位置，小于 target 3，此时让left = mid + 1那么就能直接跳出循环。
       *                            查找 1 ；同样的mid在 2 的位置， 大于 target 3 让 right = mid - 1 直接就能跳出循环。
       *           在数组：[1,2]    查找 2 ： mid 在1的位置，小于target 2， 让 left = mid + 1 也能跳出循环。

有重复数字报错了；

补救

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  /**     
* 以上的题解都是在假设数组中没有重复元素的情况下如何去二分查找
   *      解决重复数字方法一：赋值 left 和 right 后把她两往前滑一滑：
   *          在依然 left < right 的情况下：
   *              判断 right 左边的 numbers[right - 1] 是否等于 numbers[right]，等于就往左滑
   *              判断 left  右边的 numbers[left + 1] 是否等于  numbers[left], 等于就往右滑
   *          其实这种处理办法还是在把重复的数字块当作一个数字，也就是说把	[10,1,10,10,10] 当作 [10,1,10]
   *
   *      解决重复数组的方法二：就是把等于这一项单列出来上面分析把大于和等于放在一起考虑。但是后来发现他们是不能放在一起考虑的：
   *          比如： [10, 1, 10, 10, 10], 这里mid在索引为 2 的位置，把大于等于放在一起考虑则就默认中间是没有小于1这种情况存在的。
   *              不如就等于时把high慢慢往下放，直到循环条件不满足时；
   *
   *
   */

补救代码一：

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
public int minArray(int[] numbers) {
    int left = 0;
    int right = numbers.length-1;
    while(left < right &&  (numbers[right-1] == numbers[right])){
        right = right-1;
    }
    while(left < right && (numbers[left+1] == numbers[left])){
        left = left+1;
    }
    while (left < right){
        int mid = left + (right - left) /2;
        if (numbers[left] < numbers[right]){
            return numbers[left];
        }
        if (numbers[mid] < numbers[left] ){
            right = mid;
            while(left < right &&  (numbers[right-1] == numbers[right])){
                right = right-1;
            }
        } else if (numbers[mid] >= numbers[left]){
            left = mid + 1;
            while(left < right && (numbers[left+1] == numbers[left])){
                left = left+1;
            }
        }
    }
    return numbers[left];
}

补救代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minArray(int[] numbers) {
    int left = 0;
    int right = numbers.length-1;
    while (left < right){
        int mid = left + (right - left) /2;
        if (numbers[left] < numbers[right]){
            return numbers[left];
        }
        if (numbers[mid] < numbers[left] ){
            right = mid;
        } else if (numbers[mid] >= numbers[left]){
            left = mid + 1;
        } else{
            left += 1;
        }
    }
    return numbers[left];
}