使用HashSet从排序数组中删除重复项

Question

我有一个问题：

对象显示给定一个排序数组，删除重复的元素，使每个元素只出现一次，并返回新的长度。不要为另一个数组分配额外的空间，必须在内存不变的情况下这样做。例如，给定输入数组Nums=[1,1,2]，你的函数应该返回长度=2，Nums的前两个元素分别为1和2。你在新的长度之外留下什么并不重要。

我使用HashSet来回答这个问题，但结果总是显示[1,1]。我想不出来有人能帮我知道问题出在哪里吗？

我的代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> numset = new HashSet<>();
        for(int i:nums){
            numset.add(i);
        }
        return numset.size();
    }
}

您的输入[1,1,2]您的答案[1,1]预期答案[1,2]

Answer 1

使用额外的数据结构也违反了您提到的规则，即不为其分配额外空间。现在，由于数组已经排序，下面的代码可以正常工作。

int solution(int[] nums) {
    int size = nums.length;
    if (size == 0 || size == 1) {
        return size;
    }
    int next = 0;

    for (int i = 0; i < size - 1; i++) {
        if (nums[i] != nums[i + 1]) {
            nums[next++] = nums[i];
        }
    }
    nums[next++] = nums[size - 1];

    return next;
}

在上面的代码中，我们只是维护了一个额外的索引（next），以便只跟踪唯一的元素，并通过覆盖非唯一的元素将它们移动到前面。

Answer 2

• 您的解决方案不是就地解决方案
• 由于使用的是散列集，因此违反了常量内存规则
• 在java中，一旦数组被初始化，我们就不能缩小它的大小

因此，对于最坏情况时间复杂度为O（n）的问题，这里有一个简单的就地解决方案。

public int removeDuplicates(int[] nums){

    int length = nums.length;
    int index = 0;

    for(int i = 0; i < length - 1; i++){
        if(nums[i] == nums[i+1]){
            nums[index++] = nums[i];
        }
    }
    // this is needed because upper for loop runs until i equals to length-2
    // in order to avoid ArrayOutOfBoundException 
    nums[index++] = nums[length-1];

    // for displaying the unique array
    /*
    for(int i = 0; i < index; i++){
        System.out.println(nums[i]);
    }
    */

    return index;
}

Answer 3

假设你有一个排序数组：

int[] nums = { 1, 2, 2, 2, 4, 5, 5, 5, 7, 7, 8 };

... walk through nums, at some read position check for being a duplicate,
... (otherwise) write it compact at the write position
... return new length

覆盖nums。

因为我不想破坏编码的任何满足感，请便...

策略：在纸上解决问题。