---

theme: juejin highlight: xcode

---

本文正在参加「金石计划 . 瓜分6万现金大奖」

前言：最近自己也开始系统的刷面试题了，算法是过不去的坎，希望自己能够坚持下去✊，同行的朋友们共勉。

题一：删除排序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

注意：不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2,_]

解题思路：双指针

因为有约束条件，不可以使用额外空间，所以这里不考虑使用字典来去重；在这里可以使用双指针，即 前指针 和 后指针。

我们可以通过遍历数组，判断两个相邻的指针所指向的值是否相等，如果不相等，则说明两者不重复，将后指针的值插入到维护的下标下。如果相等，则不处理。

需要注意下标越界；

时间复杂度：O(n)\ 空间复杂度：O(1)

代码

Swift func removeDuplicates(_ nums: inout [Int]) -> Int {     var startIndex = 0     for index in 0..<nums.count-1 {         if nums[index] != nums[index+1] {             startIndex+=1             nums[startIndex] = nums[index+1]         }     }     return startIndex+1 }

题二：翻转数组

给你一个数组，将数组中的元素向右轮转 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] ```

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

解题思路：环形翻转、多次翻转、临时数组

解法一：环形翻转

以输入一为例： 1,2,3,4,5,6,7, k = 3

1 ——> 4, 4 ——> 7, 7 ——> 3, 3 ——> 6, 6 ——> 2, 2 ——> 5, 5 ——> 1,

输出：5,6,7,1,2,3,4

环形翻转的思路就是以上流程的演变。

将第0位的值向右移动k，然后将k位置下的值移动到k + k位置下，依次循环替换； \ 在替换前需要缓存后者的值，替换完之后，将操作的指针后移；

另外需要考虑到 nums.length%k=0 的情况，被整除了会在几个元素中循环；（被整除的情况下，仅在个别元素中来回翻转，并不能形成一个大环）

以输入二为例： -1, -100, 3, 99, k = 2

-1 ——> 3, 3 ——> -1, -1 ——> 3, ...

输出：-1， -100， -1， 99

如果这里没考虑到nums.length%k=0被整除的情况，就会出现以上的问题，在这里可以添加一个字典来缓存已经访问过的下标。如果出现命中缓存的情况，就从它的下一位开始。

综合以上的情况可以得出以下的思路，

代码

```swift func rotate(_ nums: inout [Int], _ k: Int) {         var index = 0;         var last = nums[index] // 前指针 用来赋值         var temp = nums[index] // 后指针 用来先保存下一个位置的值         var visiter = Int:Int // 访问过的下标集合         for _ in 0..<nums.count {             // 移动下标计算             // index = index+k < nums.count ? index+k : (index+k)%nums.count => index = (index+k)%nums.count             index = (index+k)%nums.count             // 如果访问过，需要打破小环；             if visiter[index] != nil {                 while visiter[index] != nil {                     index+=1;                 }                 last = nums[index]                 index = (index+k)%nums.count             }

/// 常规操作：             /// 先把后指针的值缓存，             /// 再把前指针的值插入后指针位置，             /// 再把缓存值返回给前指针，保证在下一轮替换前，index和前指针的值同步；             temp = nums[index]             nums[index] = last             last = temp             visiter[index] = index;         }     } ```

解法二：多次翻转

这里需要通过三次翻转，即可完成；

第一次：因为数组元素往右移动，所以肯定有元素会被移动到左边，这里先做一次整体翻转；\ 第二次：通过移动值与长度值取余（k%n），得出分界线，前翻转范围（0，（k%n）-1），在此范围内的元素翻转；\ 第三次：最后将后翻转范围（k%n，n-1）内的元素进行翻转；

代码

```swift func rotate(_ nums: inout [Int], _ k: Int) { let index = k%nums.count reverse(&nums, 0, nums.count-1) reverse(&nums, 0, index-1) reverse(&nums, index, nums.count-1) }

func reverse(_ nums: inout [Int], _ start: Int, _ end: Int) { var start = start var end = end while (start < end) { nums.swapAt(start, end) start += 1 end -= 1 } } ```

解法三：临时数组

使用一个临时数组存放原数组的值，然后再把临时数组的值赋值给原数组，不过这里还需要将每个元素往后移动k位。下标可以通过(i + k) % length来计算；

题三：存在重复元素

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

示例 1： 输入： nums = [1,2,3,1] 输出： true 示例 2： 输入： nums = [1,2,3,4] 输出： false

解题思路：排序法、集合法

第一种思路： 如果给你的是一个排序后的数组，判断它是否存在重复元素是不是很简单，使用双指针判断就可以了。

第二种思路： 如果条件允许，使用键值（key-value）的集合去缓存数组中的元素，使用元素值当作key，如果下次被命中，同样可以知道数组存在重复元素。

第三种思路： 如果你知道无序集合set的话，你就知道无序集合不存在重复元素，那么这是不是也是一种思路呢？😏

二和三的思路都是借助集合的形式，只是方式上有些不同。

解法一：排序法

将一个数组排序后，通过双指针遍历数组，若两个相邻的指针（i，i+1）数值相同，则存在重复元素，返回true，如果不重复，则指针同时向后移动； 如果遍历完也没有重复，返回false。

代码

swift func containsDuplicate2(_ nums: [Int]) -> Bool { var newNums = nums newNums.sort() for i in 0..<nums.count-1 { if newNums[i] == newNums[i+1] { return true } } return false }

解法二：集合法

利用字典的特性，可以将数组元素的值作为字典的key。当你发现key键下已经存在时，证明已经存在重复数据。

代码

swift func containsDuplicate(_ nums: [Int]) -> Bool { var numDict = [Int: Int]() for num in nums { if numDict[num] == nil { numDict[num] = num } else { return false } } return true }

题四：只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ： ``` 输入：nums = [2,2,1] 输出：1

```

示例 2 ： 输入：nums = [4,1,2,1,2] 输出：4

解题思路：位运算

如果说你只看标题，没有注意下面的要求，那么你可能会觉得就这。。。

找出不重复的元素并不难，即便是使用线性时间复杂度一样也有很多方法可以解决。但是难在该算法只使用常量额外空间。也就是我们不用借助外部空间去实现。

话说回来，有什么好的解题思路呢，答案就是位运算。通过使用位运算中的异或操作符即可。

异或：

数学符号：⊕\ 编程符号：^

任何数和它自己异或都是0， a ⊕ a = 0\ 任何数和0异或都是它自己， a ⊕ 0 = a\ 异或运算满足交换律和结合律， a ⊕ b ⊕ a =  a ⊕ a ⊕ b = 0 ⊕ b = b

代码

swift func singleNumber(_ nums: [Int]) -> Int { var result = 0 for num in nums { result ^= num } return result }