循转数组相关题目
洪笳淏 Lv4
 2021-09-12 18:30:00      

  本文是对旋转数组类型的题目的总结，一共6道，基本都是二分法的套路。

189. 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

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

示例 1:

1
2
3
4
5
6
输入: 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]

示例 2:

1
2
3
4
5
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

解题思路：

方法一：使用额外的数组

  可以使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)%n 的位置，最后将新数组拷贝至原数组即可。

1
2
3
4
5
6
7
func rotate(nums []int, k int) {
    newNums := make([]int, len(nums))
    for i, v := range nums {
        newNums[(i+k)%len(nums)] = v
    }
    copy(nums, newNums)
}

方法二：环状替换

  从另一个角度，我们可以将被替换的元素保存在变量 temp 中，从而避免了额外数组的开销。我们从位置 0 开始，最初令 temp=nums[0]。根据规则，位置 0 的元素会放至 (0+k)%n的位置，令 x=(0+k)%n，此时交换 temp 和 nums[x]，完成位置 x 的更新。然后，我们考察位置 x，并交换 temp 和 nums[(x+k)%n]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0。

  容易发现，当回到初始位置 0 时，有些数字可能还没有遍历到，此时我们应该从下一个数字开始重复的过程，可是这个时候怎么才算遍历结束呢？我们不妨先考虑这样一个问题：从 0 开始不断遍历，最终回到起点 0 的过程中，我们遍历了多少个元素？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func rotate(nums []int, k int) {
    n := len(nums)
    k %= n
    for start, count := 0, gcd(k, n); start < count; start++ {
        pre, cur := nums[start], start
        for ok := true; ok; ok = cur != start {
            next := (cur + k) % n
            nums[next], pre, cur = pre, nums[next], next
        }
    }
}

func gcd(a, b int) int { // 需要遍历的次数是n和k的最大公约数
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

方法三：数组翻转

1
2
3
4
5
6
nums = "----->-->"; k =3
result = "-->----->";

reverse "----->-->" we can get "<--<-----"
reverse "<--" we can get "--><-----"
reverse "<-----" we can get "-->----->"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func rotate(nums []int, k int)  {
    k %= len(nums)
    reverse(nums)
    reverse(nums[:k])
    reverse(nums[k:])
    return
}

func reverse(a []int) {
    n := len(a)
    for i:=0; i<n/2; i++ {
        a[i], a[n-i-1] = a[n-i-1], a[i]
    }
}

在旋转数组里寻找最小值

  可以看作寻找最小值左边界问题(直接解决又重复元素的情况)。

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

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

示例 2：

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

示例 3：

1
2
3
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路：

  本题可以看作是找数组中的最小数。如果更改一下题目条件，数组中的元素是可以重复的，那么可以看作找最小数的左边界即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func findMin(nums []int) int {
    left := 0
    right := len(nums)-1

    for left < right {
        mid := left + (right-left)/2
        if nums[right] > nums[mid] {
            right = mid
        } else if nums[right] < nums[mid] {
            left = mid+1
        } else {  // 可能因为重复元素使得两者相等，缩小查找范围
            right--
        }
    }
    return nums[left]
}

154. 寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
  • 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

1
2
输入：nums = [1,3,5]
输出：1

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路：

  同上题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func findMin(nums []int) int {
    var(
        left = 0
        right = len(nums)-1
    )

    for left < right {
        mid := left + (right-left)/2
        if nums[right] > nums[mid] {
            right = mid
        } else if nums[right] < nums[mid] {
            left = mid+1
        } else {
            right--
        }
    }
    return nums[left]
}

在旋转数组里寻找指定的值

  上面两道题是在旋转数组里寻找最小值，下面两道题是在旋转数组里寻找指定的值，这两道题的区别也是存不存在重复值。

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：nums = [1], target = 0
输出：-1

提示：

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -10^4 <= target <= 10^4

解题思路：

  其实方法还是类似于上题，不过对于寻找特定的数，需要判断该数可能存在于什么区间内。

  • 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
  • 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在[l, mid - 1] 中寻找。
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
func search(nums []int, target int) int {
    var(
        left = 0
        right = len(nums)-1
    )

    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[right] >= nums[mid] { // 右半部分是有序的
          // 此处若出现nums[right] = nums[mid]的情况，说明mid=right，因为数组不重复
            if nums[mid] < target && nums[right] >= target {
                left = mid+1
            } else {
                right = mid-1
            }
        } else if nums[right] <= nums[mid] { // 左半部分是有序的
            if nums[left] <= target && nums[mid] > target {
                right = mid-1
            } else {
                left = mid+1
            }
        }
    }
    return -1
}

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

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

示例 1：

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

示例 2：

1
2
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

解题思路：

  大体上同上题思路是一致的，只需要在遇到nums[mid]==nums[right]时缩小查找范围即可。

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
func search(nums []int, target int) bool {
    var(
        left = 0
        right = len(nums)-1
    )

    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        } else if nums[mid] == nums[right] || nums[left] == nums[right] {
          // 当收尾元素相等或中值与末尾元素相等时，缩小查找范围
            right--
        } else if nums[mid] < nums[right] {
            if nums[mid] < target && nums[right] >= target {
                left = mid+1
            } else {
                right = mid-1
            }
        } else if nums[mid] > nums[right] {
            if nums[left] <= target && nums[mid] > target {
                right = mid-1
            } else {
                left = mid+1
            }
        } 
    }
    return false
}

面试题 10.03. 搜索旋转数组

搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

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

示例2:

1
2
输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 输出：-1 （没有找到）

提示:

  1. arr 长度范围在[1, 1000000]之间

解题思路：

  本题是上一题的一个小进阶，不仅要确认是否有target值，还要输出其左边界，在上一题的基础上套用二分法查找左边界的方法即可。

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
func search(arr []int, target int) int {
    var(
        left = 0
        right = len(arr)-1
    )

    for left < right {
        mid := left + (right-left)/2

        if arr[mid] == target { // 找到目标后用右边界锁定住
            right = mid
        } else if arr[left] == arr[right] || arr[mid] == arr[right] { // 排除重复数，缩小搜索范围
            right--
        } else if arr[right] > arr[mid] {
            if arr[mid] < target && arr[right] >= target {
                left = mid+1
            } else {
                right = mid
            }
        } else if arr[right] < arr[mid] {
            if arr[left] <= target && arr[mid] > target {
                right = mid
            } else {
                left = mid+1
            }
        }
    }
    if arr[left] == target {
        return left
    }
    return -1
}
  • Post title：循转数组相关题目
  • Post author：洪笳淏
  • Create time：2021-09-12 18:30:00
  • Post link：https://jiahaohong1997.github.io/2021/09/12/循转数组相关题目/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments