Leecode-配列から重複を削除
2217 ワード
原文住所:https://www.luoyangfu.com/art...
タイトル
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例1:
例2:
配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.説明:
なぜ返される数値は整数ですが、出力される答えは配列ですか?
入力配列は「参照」で渡されます.これは、関数で入力配列を変更することが呼び出し元に表示されることを意味します.
内部操作は次のように想像できます.
構想
テーマの説明によると:ソート配列->配列は秩序化された 重複配列をその場で削除-> は削除できません.各要素に1回のみ現れる->時間複雑度O(n) 追加の配列スペースを使用できません->要素をコピーできません 配列の長さを超えるデータを考慮する必要がない->第2条に対応して、除去する要素を後の に置く.
二重ポインタは、その名の通り、二つのポインタを用いて配列を遍歴することであり、一般的に、遍歴配列は単一ポインタ(index)で遍歴し、二つのポインタは一般的に秩序配列で使用され、一つは頭を置き、一つは尾を置き、同時に中間に遍歴し、二つのポインタが交差するまで遍歴し、遍歴を完了し、時間の複雑さもO(n)である.
解決策
解決策に基づいて、ここでは
上記のコードには2つの解釈があり、
タイトル
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例1:
nums = [1,1,2],
2, nums 1, 2。
。
例2:
nums = [0,0,1,1,1,2,2,3,3,4],
5, nums 0, 1, 2, 3, 4。
配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.説明:
なぜ返される数値は整数ですが、出力される答えは配列ですか?
入力配列は「参照」で渡されます.これは、関数で入力配列を変更することが呼び出し元に表示されることを意味します.
内部操作は次のように想像できます.
// nums “ ” 。 ,
int len = removeDuplicates(nums);
// 。
// , 。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
構想
テーマの説明によると:
O(n)
の場合、秩序化された配列を削除する必要があります.カウント変数i = 0
を使用して、現在の配列が重複していないデータをマークします.しかし、この場合、
の配列が必要です.この場合、重複したデータを後ろに置く必要があります.このようにして返されたデータは、前のi
個のデータが重複しないように保持することができる.後の要素と交換する必要がある以上、配列交換には2つの下表が必要であり、ここでは現在の配列遍歴カウント変数として別の j
を用いて表す.上記の説明によれば、我々が使用する方法は
とも呼ばれる.ここではi
をスローポインタ、j
をクイックポインタと呼ぶ二重ポインタは、その名の通り、二つのポインタを用いて配列を遍歴することであり、一般的に、遍歴配列は単一ポインタ(index)で遍歴し、二つのポインタは一般的に秩序配列で使用され、一つは頭を置き、一つは尾を置き、同時に中間に遍歴し、二つのポインタが交差するまで遍歴し、遍歴を完了し、時間の複雑さもO(n)である.
解決策
解決策に基づいて、ここでは
javascript
文法を使用して開発します.function removeDuplicates(arr) {
if(!Array.isArray(nums) || !nums.length) return 0;
if(nums.length < 2) return 1;
var i = 0;
for(var j = 1; j < nums.length; j ++) {
if(nums[i] !== nums[j]) {
i ++;
nums[i] = nums[j]
}
}
return ++i;
}
上記のコードには2つの解釈があり、
nums[i] !== nums[j]
と判断する.ここで、彼らが等しくない場合はi
とj
の位置交換を行い、同じ場合はj
が同じ要素をスキップし、i++
は異なる次の要素で交換する.最後に++i
に戻るここでは、iは0から始まると考えるので、長いは+1が必要となる.