RemoveDuplicatesFromSortedArrayII [source code]

public class RemoveDuplicatesFromSortedArrayII {
static
/******************************************************************************/
class Solution {
    public int removeDuplicates(int[] nums) {
        int read = 0, write = -1, write_len = 0;
        while (read < nums.length) {
            if (read == 0 || nums[write] != nums[read]) {
                nums[++write] = nums[read];
                write_len = 1;
            } else if (nums[write] == nums[read] && write_len < 2) {
                nums[++write] = nums[read];
                write_len++;
            }
            read++;
        }
        return write + 1;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RemoveDuplicatesFromSortedArrayII.Solution tester = new RemoveDuplicatesFromSortedArrayII.Solution();
        int[][] inputs = {
            {1,1,1,2,2,3},{1,1,2,2,3},{5},
            {1,2,2},{1,2,2},{3},
            {1,2,2,2,2},{1,2,2},{3},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i];
            String input_str = Printer.array (nums);
            int[] ans = inputs[3 * i + 1];
            int ans_len = inputs[3 * i + 2][0];
            System.out.println (Printer.separator ());
            int output_len = tester.removeDuplicates (nums);
            String output_str = String.format ("[%s] and %d", Printer.array (nums), output_len), ans_str = String.format ("[%s] and %d", Printer.array (ans), ans_len);
            System.out.printf ("[%s] -> %s, expected: %s\n", 
                input_str, Printer.wrap (output_str, check (nums, output_len, ans, ans_len) ? 92 : 91), ans_str
            );
        }
    }

    static boolean check (int[] nums, int output_len, int[] ans, int ans_len) {
        if (nums.length < ans_len || ans.length != ans_len || output_len != ans_len)
            return false;
        for (int i = 0; i < ans_len; i++) if (ans[i] != nums[i])
            return false;
        return true;
    }
}

downvote比较多, 但是又看不出来坑在哪里; 先随便写写;

另外, 之前学分段算法的时候经常就觉得我对于利用prev这样的分段算法太过于执迷, 而多于比较直接的neighbor access反而不熟练, 所以这一题干醋就正好着重锻炼一下这种写法风格;

一开始想用一个1pass的类似思路来做, 但是做着做着感觉有点麻烦, 想到一个办法, 先把所有需要除掉的duplicate用一个boolean array给标记出来, 然后再用move zero的思路重新压缩一边就行了; 但是这个算法的弊端就是需要2pass, 而且有额外的空间cost;

我一开始的1pass的思路是一个类似分段的思路, 站在一个run的开头, 找到这个run的尽头, 然后后面的部分都shift, 但是笔算了一下之后发现这个算法的time复杂度实在是太差了;

先想想第一题怎么做的? 那个实际上就是write和read两个快慢指针, 然后read每次读到一个新的数字, 就丢给write, 这个思路在这题能够扩展使用吗?

最后还是想出来一个好的办法, 代码也算干净, 就是超时了; 速度是1ms (19%);

注意我这里代码的处理, 与普通的2pointer算法不同, 我这里选择让write是一个inclusive的index: 也就是说0..write是已经写完的部分, 而write+1才是next position to write at; 之所以这样设计是因为想要随时能够access the previously written number; 代码其他部分稍微改动一下就行了; 当然了, iteration0开始之前, write肯定应该是-1, 因为是inclusive: 0..write在iteration0之前当然应该是Empty的;

感觉这个题目还可以啊, 怎么这么多downvote;


没有editorial;


https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27976/3-6-easy-lines-C++-Java-Python-Ruby

Same simple solution written in several languages. Just go through the numbers and include those in the result that haven’t been included twice already.
C++

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

Java

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

Python

def removeDuplicates(self, nums):  
    i = 0  
    for n in nums:  
        if i < 2 or n > nums[i-2]:  
            nums[i] = n  
            i += 1  
    return i

Ruby

def remove_duplicates(nums)  
    i = 0  
    nums.each { |n| nums[(i+=1)-1] = n if i < 2 || n > nums[i-2] }  
    i  
end

果然这个方法非常的精炼; 这个时候我的方法也就显得有点笨重了; discussion第一页标题看到一些extend到K的算法, 这时候就知道为什么他们要这么做了, 他们肯定想到的是和我一样的思路: 维持一个len这样不用频繁的回头: 在K的情况下, 定点回头未必那么简单;

不对哦, 人家这个算法也可以扩展到K的;

Just want to confirm, this solution can be easily generalized to “at most K duplicates”, right?

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

顺便:

用上下箭头来表示2pointer的技巧应该很熟悉了, 这个在没有彩色笔的情况下很有帮助;


https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27970/Share-my-O(N)-time-and-O(1)-solution-when-duplicates-are-allowed-at-most-K-times

I think both Remove Duplicates from Sorted Array I and II could be solved in a consistent and more general way by allowing the duplicates to appear k times (k = 1 for problem I and k = 2 for problem II). Here is my way: we need a count variable to keep how many times the duplicated element appears, if we encounter a different element, just set counter to 1, if we encounter a duplicated one, we need to check this count, if it is already k, then we need to skip it, otherwise, we can keep this element. The following is the implementation and can pass both OJ:

int removeDuplicates(int A[], int n, int k) {  
    if (n <= k) return n;  

    int i = 1, j = 1;  
    int cnt = 1;  
    while (j < n) {  
        if (A[j] != A[j-1]) {  
            cnt = 1;  
            A[i++] = A[j];  
        }  
        else {  
            if (cnt < k) {  
                A[i++] = A[j];  
                cnt++;  
            }  
        }  
        ++j;  
    }  
    return i;  
}

跟我的几乎是没有区别的, 不过他的i定义的是一个exclusive position; 反正稍微改一下, 其实本质上是一样的;

This is my short and easy to understand solution for the problem where duplicates are allowed at most k times.
My approach is to remain first k elements as it is . Now start from k'th index and check if the element at the position current index - k is
the same as new arriving element then skip this element and continue with next element . here the condition nums[j-k]!=nums[i] is very important because
if i will use i in place of j i.e. nums[i-k]!=nums[i] then it will give wrong answer because we have to look k steps backward in new updated array.
please comment if any test case fails

int removeDuplicates(vector<int>& nums,int k) {  
    if(nums.size()<k) return nums.size(); // if array size is less than k then return the same  
    int i,j;  
    for(i=k,j=k ; i<nums.size();i++)  
        if(nums[j-k]!=nums[i]) nums[j++]=nums[i];  
    return j;  
}

基本就跟Stefan那个方法是一样的;


https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/28067/O(N)-Time-and-O(1)-Java-Solution-When-Allowed-at-Most-K-times-of-Duplicates

Share my general solution for “Remove Duplicates Problem”.

If anyone could think of a better solution please let me know.

public int removeDuplicates(int[] nums) {  
    //define at most k times of duplicate numbers  
    final int k = 2;  

    //check if it is an empty array  
    if(nums.length == 0) return 0;  

    //start pointer of new array  
    int m = 1;  

    // count the time of duplicate numbers occurence  
    int count = 1;  

    for(int i = 1; i < nums.length; ++i) {  
        if(nums[i] == nums[i - 1]) {  
            if(count < k) {  
                nums[m++] = nums[i];  
            }  
            count++;  
        } else {  
            count = 1;  
            nums[m++] = nums[i];  
        }  
    }  
    return m;  
}

类似的, 代码的组织换了一下而已;


submission基本波动, 不过就都是这个速度了;

另外, 一遍看下来, 才发现都没有人使用我想的那个O(N)space的move zero的思路; 不过有时候, 这样给自己降低一下难度也不是什么十足的坏事;


Problem Description

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.

Difficulty:Medium
Total Accepted:141.6K
Total Submissions:386K
Contributor:LeetCode
Companies
facebook
Related Topics
arraytwo pointers

results matching ""

    No results matching ""