Leetcode — 旋转数组(二分查找)

时间:2021-7-3 作者:qvyue

1.旋转数组(189 – 中)

题目描述:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

进阶:

  • 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

示例 :

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

思路:多解法,其中使用额外数组,空间复杂度O(N),其余O(1)。

  • 使用额外数组:遍历原数组,将原数组下标为 ii 的元素放至新数组下标为 (i+k)%n 的位置,最后将新数组拷贝至原数组即可。
  • 模拟循环:用一个变量tmp维护移动k次,时间复杂度O(kn)。
  • 数组翻转:比较巧妙,先整体翻转,在将0 ~ k – 1和k – 1 ~ n – 1进行反转。

还有更多类似环状替换等解法,待补充…

代码实现:

// 使用辅助空间
public void rotate(int[] nums, int k) {
    int n = nums.length;
    int[] newArr = new int[n];
    for (int i = 0; i  0; j--) {
            nums[j] = nums[j - 1];
        }
        nums[0] = temp;
    }
}

// 数组翻转
public void rotate(int[] nums, int k) {
    int n = nums.length;
    k %= n;
    reverse(nums, 0, n - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, n - 1);
}
public void reverse(int[] nums, int i, int j) {
    int tmp;
    while (i 

2.寻找旋转排序数组中的最小值(153 – 中)

题目描述:整数数组 nums 按升序排列,数组中的值 互不相同 。请你找出并返回数组中的 最小元素

示例 :

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

思路:本题可以直接遍历获取最小值,但是考察点二分查找。注意体会二分查找的思想,不要背模板,这里可以画个折线看看。

注:代码中比较元素取数组最后一个元素,也可以取任意一个元素。

代码实现:

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

3.寻找旋转排序数组中的最小值II(154 – 难)

题目描述:整数数组 nums 按升序排列,数组中的值 可能存在重复值 。返回数组中的 最小元素

示例 :

输入:nums = [2,2,2,0,1]
输出:0

思路:本题可以直接遍历获取最小值,但是考察点二分查找,与上题不同的是数组中可能含有重复值,但是二分的本质是二段性,并非单调性,所以我们还以使用二分。但时间复杂度可能退化O(n),即全部是一种元素。

代码实现:

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

4.搜索旋转排序数组(33 – 中)

题目描述:整数数组 nums 按升序排列,数组中的值 互不相同

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

示例 :

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4

思路:可以按照153题找到最小值索引,即分成两段有序数组,这样就回到有序数组的二分查找。

其实,也可以直接进行二分查找:我们使用mid划分的两部分一定有一部分是有序的,那么我们再根据目标值是否在有序区间。

注意:本题为了代码简洁,将进入条件改成while(l

代码实现:

public int search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l > 1);
        if (nums[mid] == target) return mid;
        if (nums[mid] > nums[r]) {
            if (target >= nums[l] && target  nums[mid] && target 

5.搜索旋转排序数组II(82 – 中)

题目描述:整数数组 nums 按升序排列,数组中的值 可能存在重复值

给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false 。

示例 :

输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true

思路:经过上述各题的过度,直接使用二分解法。

时间复杂度:对于这种含重复元素的二分查找问题,最坏时间复杂度O(n),即整个数组都是同一个数,最好时间复杂度O(nlogn)。

代码实现:

public boolean search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l > 1);
        if (nums[mid] == target) return true;
        if (nums[mid] > nums[r]) {
            if (target >= nums[l] && target  nums[mid] && target 

6.在排序数组中查找目标值的首尾元素的索引(34 – 中)

题目描述:给定一个按照升序排列的整数数组 nums,可能含有重复值,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1, -1]。

要求:你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 :

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

思路:代码1在极端情况下,时间复杂度退化为O(n),不符合要求,但容易理解,实现简单。

其实,我们只需要找两个索引即可,大于target – 1的索引(即目标值的起始索引)和第一个大于target的数的索引 – 1,时间复杂度O(nlogn),只调用了两次二分查找。

代码实现:

// 代码1
public int[] searchRange(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l > 1);
        if (nums[mid] == target) {
            int start = mid, end = mid;
            while (start >= 0 && nums[start] == target) start--;
            while (end  target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return new int[] {-1, -1};
}

// 代码2
public int[] searchRange(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    int leftIdx = binarySearch(nums, target - 1);
    int rightIdex = binarySearch(nums, target) - 1;
    if (leftIdx > 1);
        if (nums[mid] > target) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

7.面试题:10.03(补充)

题目描述:返回目标元素的第一个索引,即索引值最小的那个(如果存在),不存在返回-1。

示例 :

 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 输出: 8(元素5在该数组中的索引)

思路:本题是T82和T34的思路的融合,但注意由于数组是经过旋转,所以不能像T34查找边界。类似这种情况旋转数组:[5,5,5,1,2,3,4,5] 目标值:5,返回的是7,却不是0。

  • 如果左边索引满足条件,直接返回
  • 二分,mid符合,但是我们找最小的,所以要更新右边界。
  • mid不符合,找升序区间继续二分

代码实现:

public int search(int[] nums, int target) {
    int n = nums.length;
    int l = 0, r = n - 1;
    while (l > 1);
        // 索引mid的值是目标值(左边可能还有更小的索引值),更新右边界
        if (nums[mid] == target) r = mid;
        if (nums[mid] > nums[l]) {
            if (target >= nums[l] && target = nums[mid] && target 

8.山脉数组的峰顶索引(852 – 易)

题目描述:符合下列属性的数组 arr 称为 山脉数组 :

  • arr.length >= 3
  • 存在 i(0
    arr[0]
    arr[i] > arr[i+1] > … > arr[arr.length – 1]

给你由整数组成的山脉数组 arr ,返回任何满足 arr[0] arr[i + 1] > … > arr[arr.length – 1] 的下标 i 。

示例 :

输入:arr = [0,2,1,0]
输出:1

思路:本题考察点二分查找,只不过二分的判断条件有点不同。即通过mid相邻点判断最大值所在区间。

代码实现:

public int peakIndexInMountainArray(int[] arr) {
    int n = arr.length;
    int l = 0, r = n - 1;
    while (l > 1);
        if (arr[mid] 

9.山脉数组中查找目标值(1095 – 难)

题目描述:给你一个 山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index,就请返回 -1。

示例 :

输入:array = [1,2,3,4,5,3,1], target = 3
输出:2
解释:3 在数组中出现了两次,下标分别为 2 和 5,我们返回最小的下标 2。

思路:上一题的升级,我们寻找包含重复元素的最小索引值。类比面试题10.03。两阶段:

  • 找到最大值索引,T852
  • 分别在升序和降序区间找目标值。

时间复杂度O(nlogn),进行三次二分查找(也可能两次)。

代码实现:

public int findInMountainArray(int target, MountainArray mountainArr) {
    // 1.查找峰顶索引
    int n = mountainArr.length();
    int l = 0, r = n - 1;
    while (l > 1);
        if (mountainArr.get(mid) > 1);
        if (mountainArr.get(mid) == target) return mid;
        if (mountainArr.get(mid) 

10.两数相除(29 – 中)

思路:由于题目限定了我们不能使用乘法、除法和 mod 运算符。

核心:我们可以先实现一个「倍增乘法」,然后利用对于 x 除以 y,结果 x / y 必然落在范围 [0, x] 的规律进行二分。

注意:long mid = l + r + 1 >> 1,之前的用法会超时?

public int divide(int a, int b) {
    long x = a, y = b;
    boolean isNeg = (x  0) || (x > 0 && y > 1;
        if (mul(mid, y)  Integer.MAX_VALUE || ans  0) {
        if ((k & 1) == 1) ans += a;
        k >>= 1;
        a += a;
    }
    return ans;
}

巨人的肩膀: @甜姨 @宫水三叶

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。