説明#
ソートされた配列が与えられた場合、重複する要素をインプレースで削除し、各要素が一度だけ現れるようにし、削除後の配列の新しい長さを返します。
余分な配列スペースを使用しないでください。インプレースで入力配列を変更し、O (1) の追加スペースを使用して処理を完了する必要があります。
例 1:
与えられた配列 nums = [1,1,2] の場合、
関数は新しい長さ2を返し、元の配列 nums の最初の2つの要素が1と2に変更されます。
新しい長さの後に配列の要素が存在することは考慮しないでください。
例 2:
与えられた配列 nums = [0,0,1,1,1,2,2,3,3,4] の場合、
関数は新しい長さ5を返し、元の配列 nums の最初の5つの要素が0、1、2、3、4に変更されます。
新しい長さの後に配列の要素が存在することは考慮しないでください。
注意:
なぜ返される値が整数であり、出力の答えが配列なのでしょうか？
入力配列は **「参照」** の形式で渡されることに注意してください。つまり、関数内で入力配列を変更すると、呼び出し元にも反映されます。
次のような内部操作を想像することができます。
// numsは「参照」の形式で渡されます。つまり、引数に対してコピーは作成されません
int len = removeDuplicates(nums);
// 関数内で入力配列を変更すると、呼び出し元にも反映されます。
// 関数の戻り値に基づいて、長さの範囲内のすべての要素が配列に印刷されます。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
アプローチ#
- 配列を後ろから前に向かって走査し、現在の要素が前の要素と同じ場合、現在の要素から配列を前に移動します
int removeDuplicates(int* nums, int numsSize){
int now_size = numsSize;//配列のサイズを記録
for(int i=numsSize-1;i>0;i--) {
if(nums[i-1] == nums[i]) {//重複する要素が見つかった場合
now_size--;//配列のサイズをデクリメント
for(int j=0;j<numsSize-i-1;j++)//配列を前に移動
nums[i+j] = nums[i+j+1];
}
}
return now_size;
}
追加#
- 配列を走査し、重複した要素を最大値または最小値に設定し、重複回数を記録し、配列のサイズから重複回数を引いたものが新しい配列のサイズです
- バブルソートで元の配列を並べ替えるだけです
void exchange(int* num1,int* num2) {
int num = *num1;
*num1 = *num2;
*num2 = num;
}
int removeDuplicates(int* nums, int numsSize){
int delete_nums = 0;
for(int i=1;i<numsSize;i++) {
if(nums[i] == nums[i-1]) {
delete_nums++;
nums[i-1] = 0x7fff;
}
}
for(int i=0;i<numsSize;i++) {
for(int j=numsSize-1;j>i;j--) {
if(nums[j] < nums[j-1])
exchange(nums+j,nums+j-1);
}
}
return numsSize-delete_nums;
}
追加 2#
- 配列がソートされているため、最終的な配列の各要素は増加し、一意であるため、最初の要素は変更する必要がありません。2 番目の要素から始めて、配列を後ろに走査し、2 番目の要素が 1 番目の要素より大きい場合、2 番目の要素と交換し、3 番目の要素に進みます
void exchange(int* num1,int* num2) {
int num = *num1;
*num1 = *num2;
*num2 = num;
}
int removeDuplicates(int* nums, int numsSize){
if(numsSize < 2)
return numsSize;
for(int now = 1,last_find = 1;;now++) {//現在の位置
for(int find = last_find;;find++) {//検索ポインタ
if(find >= numsSize)//検索終了
return now;
if(nums[find] > nums[now-1]) {//指定の要素が見つかった場合
if(find != now)
exchange(nums+now,nums+find);
last_find = find + 1;//次回の検索は次の要素から開始
break;
}
}
}
}
- この方法では、以前の方法よりもはるかに効率が向上しています