今日题目有：

  • 轮转数组
  • 存在重复元素

1. 轮转数组

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例：

输入: 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]

方法一： 辅助空间法

思路

  • k←k%n，将k限定在[0,n−1]范围内。
  • 用i表示轮转前位置，i′表示轮转后位置。

对于数取模，有： $$ a \% b = \begin{cases} a, & a\leq b-1 \\ a-b*k，& a\geq b \ \end{cases} $$
因此，我们有： $$ i^,=(i+k)\%n = \begin{cases} i+k, & i+k\leq n-1 \\ i+k-n，& i+k\geq n \ \end{cases} $$

  • 基于此，我们拷贝源数组，根据上面发现的下标关系，进行数组遍历和赋值。

Code

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        origin_nums = copy.deepcopy(nums)
        len_of_nums = len(nums)
        k = k % len_of_nums
        for index in range(0, len(nums)):
            if index + k >= len_of_nums:
                nums[index+k-len_of_nums] = origin_nums[index]
            else:
                nums[index+k] = origin_nums[index]

方法二：双指针 + 翻转数组

refer from TsingPig老师

思路

  • 先整体翻转数组，即翻转[0, n-1]区间
  • 然后分别翻转[0, k-1]和[k, n-1]区间即为 结果

正确性证明：

Code

def reverse(nums: List[int], left: int, right: int) -> None:
    i, j = left, right
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1


class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        reverse(nums, 0, n - 1)
        reverse(nums, 0, k - 1)
        reverse(nums, k, n - 1)

2. 存在重复元素

题目描述

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

思路

比较简单，看set长度 or 排序再遍历 Code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums)!=len(set(nums))

    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        for idx in range(0, len(nums)-1):
            if nums[idx] == nums[idx+1]:
                return True
            else:
                idx+=1
        return False