leetcode刷題記錄--【80 Remove Duplicates from Sorted Ar

haobowd 發(fā)布于2019-08-19 11:46 / 2917人閱讀

摘要：給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長(zhǎng)度。正確思路對(duì)于每一個(gè)元素，都進(jìn)行移動(dòng)。或者比較不到最后一個(gè)對(duì)象。

給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

錯(cuò)誤思路：
由26題跳過一個(gè)的思路，很自然的聯(lián)想到跳過2個(gè)即可。但是對(duì)于{0，0,1,1,1,1,2,3,3}這種情況，最后一個(gè)3無法被放到前面去，結(jié)果是{0,0,1,1,2,3,2,3,3}，這是因?yàn)殄e(cuò)誤代碼將第一個(gè)不同的值移動(dòng)到正確位置以后，下一個(gè)和剛被移動(dòng)的這個(gè)值比對(duì)如果相同的話，是要等待下一次移動(dòng)的，而下一次已經(jīng)到了數(shù)組末尾，不再進(jìn)行移動(dòng)操作。
所以增加針對(duì)最后一個(gè)元素的處理（因?yàn)槲抑幌氲搅俗詈笠粋€(gè)元素可能和剛被移動(dòng)的元素相同的情況），但是又引發(fā)了一個(gè)bug，即{1,1,1,2,2,3}->{1,1,2,2,3,3},當(dāng)全部移動(dòng)完成后，我會(huì)多帶帶去比較最后一個(gè)元素是否和剛被移動(dòng)的相同，相同的話，直接放到剛被正確安放的元素后，這樣就導(dǎo)致了重復(fù)數(shù)據(jù)的出現(xiàn)。

public static int removeDuplicates(int[] nums)
{
    int i = 0, j = 0, count=1;
    for(i = 1; i < nums.length; i++)
    {
        if(nums[i] != nums[j])
        {
            if (count >= 2)
            {
                j = j + 2;
                nums[j] = nums[i];
            }
            else
            {
                j = j + 1;
                nums[j] = nums[i];
            }
            count = 1;
        }
        else
        {
            count++;
        }
    }
    if (nums[nums.length - 1] == nums[j])
    {
        j = j + 1;
        nums[j] = nums[nums.length - 1];
    }
    System.out.println(j+1);
    return j+1;
}

正確思路：

public int removeDuplicates(int[] nums)
{
    int i = 0, j = 0, count=1;
    for(i = 1; i < nums.length; i++)
    {
        if(nums[i] == nums[i-1])
        {
            count++;
        }
        else
        {
            count = 1;
        }

        if (count <= 2)
        {
            j = j + 1;
            nums[j] = nums[i];
        }
    }
    System.out.println(j+1);
    return j+1;
}

1.對(duì)于每一個(gè)元素，都進(jìn)行移動(dòng)。
2.計(jì)算相同的個(gè)數(shù)，相同的數(shù)量在2個(gè)以上時(shí)，就不進(jìn)行移動(dòng)
3.不是比較nums[i]和nums[i+1]，因?yàn)檫@樣會(huì)導(dǎo)致溢出，參見26題的錯(cuò)誤思路。或者比較不到最后一個(gè)對(duì)象。