26.並べ替え配列から重複項目を削除する
1517 ワード
タイトル:
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
考え方1:
配列が整列し、
a、だから重複する数値の個数を記録して、ここでkを使って記録します
k値に基づいて現在値を前に移動します.これは、前の繰り返し値を除去した後に現在値が存在するべき位置です.
b、配列が重複しない数字の個数を記録し、後の重複しない数字を個数に1を加え、配列の中に置けばよい.
考え方2:
set関数の使用
構想1コードは以下の通りです(python):
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
考え方1:
配列が整列し、
a、だから重複する数値の個数を記録して、ここでkを使って記録します
k値に基づいて現在値を前に移動します.これは、前の繰り返し値を除去した後に現在値が存在するべき位置です.
b、配列が重複しない数字の個数を記録し、後の重複しない数字を個数に1を加え、配列の中に置けばよい.
考え方2:
set関数の使用
構想1コードは以下の通りです(python):
def removeDuplicates(self,nums):
if len(nums)>0:
j = nums[0]
else:
return 0
k = 0 #
i = 1
while i < len(nums):
if nums[i] == j:
k = k + 1
else:
j = nums[i]
nums[i - k] = nums[i] #
i = i + 1
return i - k
int removeDuplicates(vector& nums) {
int i = !nums.empty();
for (int n : nums)
if (n > nums[i-1])
nums[i++] = n;
return i;
}
// i ,i , 。
// , , ,
int removeDuplicates(int* nums, int numsSize)
{
int pre = 0, cur = 0;
if (numsSize == 0)
return 0;
while (cur < numsSize)
{
if (nums[pre] == nums[cur])
{
cur++;
}
else
{
nums[++pre] = nums[cur++];
}
}
return pre + 1;
// , ,