---

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 }