26.並べ替え配列から重複項目を削除する

1517 ワード

タイトル:
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が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;
//         ,            ,