搜索旋转排序数组「变题」

本篇文章仅汇总该系列的变题！！！关于搜索旋转排序数组的原理可见 浅析：搜索旋转排序数组

变题一：无重复元素寻找目标值

题目详情可见 搜索旋转排序数组

x
// 写法一
public int search(int[] nums, int target) {
    int n = nums.length, l = 0, r = n - 1;
    while (l < r) {
        int m = l + r + 1 >> 1;
        if (nums[m] == target) return m;
        if (nums[m] <= nums[r])
            if (nums[m] <= target && target <= nums[r]) l = m;
        else r = m - 1;
    } else {
        if (nums[l] <= target && target <= nums[m]) r = m;
        else l = m + 1;
    }
}
return nums[l] == target ? l : -1;
}
// 写法二
public int search(int[] nums, int target) {
    int n = nums.length, l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (nums[m] == target) return m;
        if (nums[l] <= nums[m]) {
            if (nums[l] <= target && target <= nums[m]) r = m;
            else l = m + 1;
        } else {
            if (nums[m] <= target && target <= nums[r]) l = m;
            else r = m - 1;
        }
    }
    return nums[l] == target ? l : -1;
}

变题二：有重复元素寻找目标值

题目详情可见 搜索旋转排序数组 II

x
public boolean search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r + 1 >> 1;
        if (nums[m] == target) return true;
        if (nums[m] == nums[r]) r--;  // 和无重复元素的类型唯一的不同点
        else if (nums[l] <= nums[m]) {
            if (nums[l] <= target && target <= nums[m]) r = m;
            else l = m + 1;
        } else {
            if (nums[m] <= target && target <= nums[r]) l = m;
            else r = m - 1;
        }
    }
    return nums[l] == target;
}

变题三：无重复元素寻找最小值

题目详情可见 寻找旋转排序数组中的最小值

xxxxxxxxxx
public int findMin(int[] nums) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (nums[m] <= nums[r]) r = m;
        else l = m + 1;
    }
    return nums[l];
}

变题四：有重复元素寻找最小值

题目详情可见 寻找旋转排序数组中的最小值 II

x
public int findMin(int[] nums) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = l + r >> 1;
        if (nums[m] == nums[r]) r--;  // 和无重复元素的类型唯一的不同点
        else if (nums[m] < nums[r]) r = m;
        else l = m + 1;
    }
    return nums[l];
}

变题五：没有找到返回大于目标值的最小值

该变题是在 搜索旋转排序数组 的基础上进行修改滴！！

• 原题的要求：若没有找到，则返回 -1
• 修改后要求：若没有找到，则返回大于 target 的最小值

🌰 举个例子：nums = [6, 7, 9, 0, 2, 4, 5], target = 8，该样例应该返回9

用变题一中的写法一可以做到部分样例可以正确返回，但有些样例返回错误，如：nums = [6, 7, 9, 0, 2, 4, 5], target = 3，错误返回5，应该返回4

这里提供一种曲线救国的方法：先找到最小值，如：变题四、变题五；然后分两段找

变题六：旋转两次

旋转一次和旋转两次是一样的，都会把一个数组分成两段递增序列

🌰 举个例子：nums = [1, 2, 3, 4, 5, 6]

先旋转一次后：nums = [3, 4, 5, 6, 1, 2]

再旋转一次后：nums = [5, 6, 1, 2, 3, 4]

变题七：手动实现旋转数组

xxxxxxxxxx
// 方法一：逐个移动
public void moveOne(int[] nums) {
    int t = nums[0], n = nums.length;
    for (int i = 1; i < n; i++) {
        nums[i - 1] = nums[i];
    }
    nums[n - 1] = t;
}

// 方法二：借助临时数组
// 从下标 idx 开始旋转数组
public void move(int[] nums, int idx) {
    int n = nums.length;
    int[] temp = new int[idx];
    for (int i = 0; i < idx; i++) temp[i] = nums[i];
    for (int i = idx; i < n; i++) {
        nums[i - idx] = nums[i];
    }
    for (int i = 0; i < idx; i++) {
        nums[n - idx + i] = temp[i];
    }
}