LeetCode 26, 80, 81, 82, . Remove Duplicates from Sorted Array/List i, ii

1.タイトルの説明
1.1 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 allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.
1.2 80 Remove Duplicates from Sorted Array II
Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice?
For example, Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.
1.3 83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
1.4 82. Remove Duplicates from Sorted List ii
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.
2.問題の解き方
2.1 Remove Duplicates from Sorted Array i, ii
これは1つのソート配列なので、2つのポインタを使って前後に移動すればいいのです
2.2 Remove Duplicates from Sorted List i, ii
直接非ソートの処理として、1つのsetまたはmapで現在の要素値の出現回数を記録し、2回目の遍歴時に該当する部分を削除すればよい.
3. code
3.1 26 Remove Duplicates from Sorted Array i
現在の値が以前に記録した値num[i d-1]と等しくない限り、彼は重複した値ではないことを示し、後方検出を継続することができる.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int id = 0;
        for (int i = 0; i != nums.size(); i++){
            if (id > 0 && nums[i] != nums[id - 1] || id == 0){
                nums[id++] = nums[i];
            }
        }

        return id;
    }
};

3.2 80 Remove Duplicates from Sorted Array ii

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int id = 0;
        for (int i = 0; i != nums.size(); i++){
            if (id > 0 && nums[i] != nums[id - 1] || id < 2 || id > 1 && nums[i] != nums[id - 2] ){
                nums[id++] = nums[i];
            }
        }

        return id;
    }
};

3.3 83. Remove Duplicates from Sorted List

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode myhead(0);
        myhead.next = head;
        ListNode * pre = &myhead;
        unordered_set<int> myset;
        while (head){
            if (myset.find(head->val) == myset.end()){
                myset.insert(head->val);
                pre = pre->next;
                head = pre->next;
            }
            else{
                pre->next = head->next;
                head = pre->next;
            }
        }
        return myhead.next;
    }
};

ソートの性質に基づいて、現在の要素と繰り返される値を削除します.

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr)
            return nullptr;

        ListNode myhead(0);
        myhead.next = head;

        int target = head->val;
        int count = 0;
        while (head->next){
            if (head->val == head->next->val){
                ListNode * tmp = head;
                while (tmp-> next && tmp->next->val == tmp->val){
                    tmp = tmp->next;
                }
                if (tmp->next == nullptr){
                    head->next = nullptr;
                    break;
                }
                head->next = tmp->next;
            }

            head = head->next;
        }

        return myhead.next;
    }
};

3.4 82. Remove Duplicates from Sorted List ii

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode myhead(0);
        myhead.next = head;
        unordered_map<int, int> mymap;
        while (head){
            mymap[head->val]++;
            head = head->next;
        }

        head = myhead.next;
        ListNode * pre = &myhead;
        while (head){
            if (mymap[head->val] > 1){
                pre->next = head->next;
                head = pre->next;
            }
            else{
                pre = pre->next;
                head = pre->next;
            }
        }

        return myhead.next;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr)
            return nullptr;

        ListNode myhead(0);
        myhead.next = head;
        ListNode * pre = &myhead;

        int target = head->val;
        int count = 0;
        while (head->next){
            if (head->val == head->next->val){
                ListNode * tmp = head;
                while (tmp->next && tmp->next->val == tmp->val){
                    tmp = tmp->next;
                }
                if (tmp->next == nullptr){
                    pre->next = nullptr;
                    break;
                }
                pre->next = tmp->next;
                head = pre->next;
                continue;
            }

            head = head->next;
            pre = pre->next;
        }

        return myhead.next;
    }
};

4.大神解法
4.1 26 Remove Duplicates from Sorted Array i

class Solution {
    public:
    int removeDuplicates(int A[], int n) {
        if(n < 2) return n;
        int id = 1;
        for(int i = 1; i < n; ++i) 
            if(A[i] != A[i-1]) A[id++] = A[i];
        return id;
    }
};

4.2 80 Remove Duplicates from Sorted Array ii
同じ考えで、もっと簡潔に表現します.

int removeDuplicates(vector<int>& nums) {
    int i = 0;
    for (int n : nums)
        if (i < 2 || n > nums[i-2])
            nums[i++] = n;
    return i;
}