我是如何給有序數(shù)組去重的？
問題
給定一個有序數(shù)組，要刪除數(shù)組重復出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，然后返回移除重復數(shù)組后的新長度；
示例：
假設給定一個數(shù)組 nums = [1,2,4,4]，刪除重復出現(xiàn)的元素 4 后，原數(shù)組變成 nums = [1, 2, 4]，此時新的數(shù)組長度為 3；
解決思路
數(shù)組原地操作
數(shù)組原地操作，此時無需創(chuàng)建新的數(shù)組，只需要在原來的數(shù)組上操作即可。相當于首先要找到數(shù)組中重復的元素，然后將重復的元素移除，此時就涉及到數(shù)組中的刪除操作，相關知識點可以看我的另一篇文章 數(shù)組的增刪改查。
這是一種時間換空間的方法，此時的空間復雜度為 ，時間復雜度為 ，具體實現(xiàn)可以參考如下代碼，其中也詳細注釋了每一步操作。
/**
* 去除有序數(shù)組中重復元素并返回數(shù)組的新長度
* @param nums
* @return 刪除重復元素后數(shù)組的新長度
*/
public int removeDuplicates(int[] nums) {
// 數(shù)組初始容量
int length = nums.length;
// 我們假定數(shù)組最后一個元素是唯一的，然后對于其他的每個元素，如果自身與它后邊的數(shù)相同，那么就刪除這個相同的元素
for(int i = length - 2; i >= 0; i++){
// 比較當前元素與其后一個元素是否相等
if(nums[i] == nums[i + 1]){
// 若相等，則移除后一位，并將所有元素向前移動一位
for(int j = i + 1; j < length; j++){
num[j - 1] = nums[j];
}
length--;
}
}
// 返回數(shù)組的新長度
return length;
}
普通方法
針對數(shù)組原地操作算法時間復雜度為 ，為降低時間復雜度提高算法效率，可以通過空間換時間的做法，通過定義新的數(shù)組，從而實現(xiàn)去除重復元素的目的，此時的時間復雜度為 ，而空間復雜度也由 變成了 。但是有幾點需要注意：
臨界情況（即數(shù)組為空）； 創(chuàng)建新數(shù)組時，需要指定其容量，所以需要先求出原數(shù)組中無重復元素時的元素個數(shù)； 最后則是將原數(shù)組中未重復的元素賦值給新數(shù)組；
/**
* 去除有序數(shù)組中重復元素并返回數(shù)組的新長度
* @param nums
* @return 刪除重復元素后的新數(shù)組
*/
public int[] removeDuplicates(int[] nums) {
// 臨界情況
if(nums.length == 0){
return nums;
}
// 先求出數(shù)組中無重復時的元素個數(shù)
int size = 0;
for(int i = 0; i < nums.length; i++){
if(i == 0 || nums[i] != nums[i - 1]){
size++;
}
}
// 用于存放不含重復元素的有序數(shù)組
int[] resultArr = new int[size];
int index = 0;
for(int i = 0; i < nums.length; i++){
if(i == 0 || nums[i] != nums[i + 1]){
resultArr[index++] = nums[i];
}
}
// 返回新的不含重復元素的有序數(shù)組
return resultArr;
}
雙指針
以上的兩種方法要么是以時間換空間，要么是以空間換時間，那我們有沒有一種折中的辦法，既能保證時間復雜度很低，也能保證空間復雜度呢？答案是：當然有！
利用雙指針的思想，既可以將空間復雜度控制在 ，也可以將時間復雜度控制在 。
/**
* 去除有序數(shù)組中重復元素并返回數(shù)組的新長度
* @param nums
* @return 刪除重復元素后數(shù)組的新長度
*/
public int removeDuplicates(int[] nums) {
// 臨界情況
if(nums.length == 0){
reutrn 0;
}
int size = 0;
for(int i = 1; i < nums.length; i++){
if(nums[size] != nums[i]){
nums[++size] = nums[i];
}
}
// 返回新長度
return size + 1;
}
總結
以上就是 3 種去除有序數(shù)組中重復元素的三種算法，其中既有以時間換空間的數(shù)組原地操作法，也有空間換時間的普通方法，最后的話則是有一種綜合前兩種方法優(yōu)點的方法 - 雙指針。通過雙指針方法，既能保證空間復雜度為 ，也將時間復雜度限制在了 。
想不到連簡單的數(shù)組去重都有這么大的學問，我們在日常學習時，大多可能只關注于如何實現(xiàn)功能即可。但如果要應用到工作場景中，可能就需要考慮效率問題，此時則需要根據(jù)我們的具體需求來進行選擇了。
好了，以上就是今天的內(nèi)容了，如果你還有其他更好的方法，歡迎留言交流呀！
