Array---Remove Duplicates from Sorted Array——移除排序數

sixgo 發布于2019-08-14 17:06 / 2560人閱讀

摘要：主要是因為數組已經是排好順序的。如果不仔細看題目，把數組當作無序數組進行操作，時會顯示超時。題目要求是不能申請二額外空間，如果提交時有申請額外空間，也是不通過的。比如對于數組，移除重復元素后為，起始數字為，而不能是其它數字。

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

思路：

（1）這道題其實很簡單。主要是因為數組已經是排好順序的。如果不仔細看題目，把數組當作無序數組進行操作，OJ時會顯示超時。

（2）題目要求是不能申請二額外空間，如果提交時有申請額外空間，也是不通過的。

（3）還需要注意的一個地方是，數組中元素的位置不能改變。比如對于數組[1,1,1,4,5]，移除重復元素后為[1,4,5]，起始數字為1，而不能是其它數字。

（4）我們只需對對組遍歷一次，并設置一個計數器，每當遍歷前后元素不相同，計數器加1，并將計數器對應在數組中位置定位到當前遍歷的元素。

算法代碼實現如下：

public static int removeDuplicates(int[] A) {
    int len = A.length;
    if (len == 0)
        return 0;
    int count = 1;
    for (int i = 1; i < len; i++) {
        if (A[i] == A[i - 1]) {
            continue;
        }else{
            A[count] = A[i];
            count++;
        }
    }
    return count;
}

上面的解法是針對有序數組，如果是無序數組，應該如何解答？

思路：

（1）如果不允許申請額外空間，則可以先對數組進行排序，為了提高效率一般考慮使用快速排序，然后再參照上面有序數組進行操作；

（2）如果允許申請空間，則只需創建一個HashSet，遍歷一次數組，通過contanins()方法進行判斷就能得到結果。

（1）和（2）所對應代碼如下所示（注：針對本文所示的題目，如果用下面代碼進行OJ，（1）會超時，（2）會產生額外空間）：

不可以申請額外空間：

public static int removeDuplicates(int[] A) {
    int len = A.length;
    if (len == 0)
        return 0;

    quickSort(A, 0, len - 1);

    int count = 1;
    for (int i = 1; i < len; i++) {
        if (A[i] == A[i - 1]) {
            continue;
        } else {
            A[count] = A[i];
            count++;
        }
    }
    return count;
}

//快速排序

private static void quickSort(int[] table, int low, int high) {
    if (low < high) {
        int i = low, j = high;
        int vot = table[i];
        while (i != j) {
            while (i < j && vot <= table[j])
                j--;
            if (i < j) {
                table[i] = table[j];
                i++;
            }
            while (i < j && table[i] < vot)
                i++;
            if (i < j) {
                table[j] = table[i];
                j--;
            }
        }
        table[i] = vot;
        quickSort(table, low, j - 1);
        quickSort(table, i + 1, high);
    }
}

可以申請額外空間：（其中，HashSet的contains()方法是用來過濾重復元素的）

public static int removeDuplicates(int[] A) {
    int len = A.length;
    HashSet set = new HashSet();
    for (int i = 0; i < len; i++) {
        if (set.size() == 0) {
            set.add(A[i]);
        }
        if (!set.contains(A[i])) {
            set.add(A[i]);
        }
    }
    return set.size();
}

云服務器 GPU云服務器 sorted-array Duplicates Sorted sorted_set

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66422.html

[Leetcode] Remove Duplicates from Sorted Array 移除有

摘要：雙指針法復雜度時間空間思路我們可以將不重復的序列存到數列前面，因為不重復序列的長度一定小于等于總序列，所以不用擔心覆蓋的問題。代碼雙指針法復雜度時間空間思路思路和上題一樣，區別在于記錄前兩個遍歷到的數字來幫助我們判斷是否出現了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...

kel 2019-08-14 12:30 評論0 收藏0
[LintCode/LeetCode] Remove Duplicates from Sorted

摘要：思路原數組長度為，則返回原數組長度不為，則至少有個元素。將所有不重復的數值賦給，而當和相等時，不做處理。最后返回的就是不同元素的個數，也是新數組的長度。只有在時，才對賦值。注意，每次初始化的時候要分兩種情況，這就意味著從的時候開始遍歷。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...

WalkerXu 2019-08-14 15:32 評論0 收藏0
leetcode 26 Remove Duplicates from Sorted Array

摘要：題目比較簡單，就是找出數組不重復的數字，返回不重復的數字個數。無需刪除重復數字，只需要保證數組的前位為不重復的個數字即可代碼如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...

alaege 2019-08-14 18:07 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
leetcode刷題記錄-【26 Remove Duplicates from Sorted Ar

摘要：給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組并在使用額外空間的條件下完成。聲明兩個指針，為快指針，為慢指針如果遇到相同的數，那么就跳過，。給定一個排序數組，你需要在原地刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。不要使用額外的數組空間，你必須在原地修改輸入數組...

heartFollower 2019-08-19 11:46 評論0 收藏0