目錄

1、消失的數字

2、旋轉數組

3、原地移除元素

4、刪除排序數組中的重復項

---

1、消失的數字

oj：面試題 17.04. 消失的數字 - 力扣（LeetCode）

思路（參考評論區）：

利用異或的特性，ret?= ret?^ x ^ x。級對同一個值異或兩次，結果等于它本身

所以對 ret?從 0 - nums.length 進行異或，同時對 nums 數組中的值進行異或，出現重復的會消失，所以最后 ret 的值是只出現一次的數字，也就是nums數組中缺失的那個數字。

class Solution {public int missingNumber(int[] nums) {int ret = 0;for(int i = 0; i < nums.length; i++) {ret ^= i;ret ^= nums[i];}ret ^= nums.length;return ret;}
}

2、旋轉數組

oj：189. 輪轉數組 - 力扣（LeetCode）

思路：

1.?使用額外的數組將每個元素放至旋轉后的位置

2.?遍歷原數組，將原數組下標為?i?的元素放至新數組下標為?(i+k)%n?的位置

3. 再把新數組寫回原數組

class Solution {public void rotate(int[] nums, int k) {int len = nums.length;int[] newArr = new int[len];for(int i = 0; i < len; i++){newArr[(i+k)%len] = nums[i];}for(int j = 0; j < len; j++){nums[j] = newArr[j];}}
}

3、原地移除元素

oj：226. 翻轉二叉樹 - 力扣（LeetCode）

思路：

1. 遍歷數組 nums，設置一個下標 ans
2. 在遍歷過程中如果出現數字不是需要被移除的值，則把這個數字覆蓋到ans所在的下標位置，ans 自增 1
3. 如果相同的時候，則跳過該數字不進行覆蓋，最后 ans 即為新的數組長度

// 時間復雜度：O(n)，空間復雜度：O(1)
class Solution {public int removeElement(int[] nums, int val) {int ans = 0;for(int i = 0; i<nums.length; i++) {if(nums[i] != val) {nums[ans] = nums[i];ans++;}}return ans;}
}

4、刪除排序數組中的重復項

oj：26. 刪除有序數組中的重復項 - 力扣（LeetCode）

思路：

1. 與上題類似，使用兩個指針，fast用于遍歷數組，slow位置用于存放不重復項

2.?在遍歷過程中如果出現數字不是重復值，則把這個數字覆蓋到slow所在的下標位置

3. slow+1 即為數組中唯一元素的數量?

class Solution {public int removeDuplicates(int[] nums) {int fast = 1;int slow = 0;for(; fast<nums.length; fast++) {if(nums[fast] != nums[slow]) {nums[slow+1] = nums[fast];slow++;}}return slow+1;}
}