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