Удалить дубликаты из отсортированного массива с помощью HashSet

Question

У меня есть проблема по этому поводу:

Объект показывает, что, учитывая отсортированный массив, удалите дубликаты на месте так, чтобы каждый элемент появлялся только один раз и возвращал новую длину. Не выделяйте дополнительное пространство для другого массива, вы должны сделать это на месте с постоянной памятью. Например, Заданные значения входного массива = [1,1,2], Ваша функция должна возвращать length = 2, причем первые два элемента чисел равны 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

• Ваше решение не является решением на месте
• Поскольку вы используете Hash Set, вы нарушаете правило постоянной памяти.
• В 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 2

Другое решение на месте. Пока нет требований хранить где-либо дублирующиеся значения и в Java нет способа сжать массив без нового массива, дубликаты заменяются на MAX_VALUE, а затем сортируются в конец массива. (см. Комментарии в коде)

Кстати: во время выполнения метода объявлена ​​переменная uniqueCount

public int removeDuplicates(int[] nums) {

 if (nums.length == 0) return 0;

// at least one element is unique
int uniqueCount = 1;

for (int i = 0; i < nums.length - 1; i++) {
    if (nums[i] == nums[i + 1]) {
    // duplicate value replaced with Integer.MAX_VALUE to be at the end of array 
    nums[i] = Integer.MAX_VALUE;
    } else {
    // nums[i] is unique
    uniqueCount++;
    }
}
// Re-sort array to move MAX_VALUE elements to the end of array
Arrays.sort(nums);
return uniqueCount;

}

Answer 3

Использование дополнительной структуры данных также является нарушением упомянутых вами правил, т. Е. Не выделяйте для этого дополнительное место.Теперь, поскольку ваш массив уже отсортирован, следующий код будет работать нормально.

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;
}

В приведенном выше коде мы просто поддерживаем дополнительный индекс (следующий), чтобы отслеживать только уникальные элементы и просто перемещатьсяих на фронт, переписывая неуникальные.

Answer 4

• Во-первых, помните, что вы не можете сжать классический массив Java в методе после присвоения .Поскольку Java является передачей по значению .
• Если вы все еще настаиваете на удалении дубликатов на месте, вам необходимо поместить разделитель, такой как Integer.MAX_VALUE или Integer.MIN_VALUE.Затем, пока значение не достигнет значения, итерируйте его или получите его размер или выполните операцию, где вам нужно.
• Тем не менее, удаление на месте кажется не очень подходящим для этой цели, поэтому я предлагаю вернуть новый массив.

Причудливое решение,

private static int removeDuplicatesWithDelimiter(int[] nums) {
    if (nums.length == 0) return 0;


    Set<Integer> numset = new HashSet<>();
    for(int i : nums){
        numset.add(i);
    }

    int newArraySize = numset.size();

    for (int i = 0; i < newArraySize; ++i) {
        nums[i] = (Integer) numset.toArray()[i];
    }

    nums[newArraySize] = Integer.MIN_VALUE;

    return newArraySize;
}

Лучшее решение,

class ArrayDuplicateTest {

    private static int[] removeDuplicates(int[] list) {
        int newLength = list.length;
        // find length w/o duplicates:
        for (int i = 1; i < list.length; i++) {
            for (int j = 0; j < i; j++) {
                if (list[i] == list[j]) {   // if duplicate founded then decrease length by 1
                    newLength--;
                    break;
                }
            }
        }

        int[] newArray = new int[newLength]; // create new array with new length
        newArray[0] = list[0];  // 1st element goes to new array
        int inx = 1;            // index for 2nd element of new array
        boolean isDuplicate;

        for (int i = 1; i < list.length; i++) {
            isDuplicate = false;
            for (int j = 0; j < i; j++) {
                if (list[i] == list[j]) {  // if duplicate founded then change boolean variable and break
                    isDuplicate = true;
                    break;
                }
            }
            if (!isDuplicate) {     // if it's not duplicate then put it to new array
                newArray[inx] = list[i];
                inx++;
            }
        }
        return newArray;
    }

    public static void main(String[] args) {
        int nums[] = {1, 1, 2, 3, 5, 6,6 ,6};

        int noDup[] = removeDuplicates(nums);

        for (int i : noDup) {
            System.out.println(i + "    ");
        }

        System.out.println("length: " + noDup.length);
    }
}

Answer 5

Скажем, у вас есть отсортированный массив:

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

Перезаписать числа.

Поскольку я не хочу портить какое-либо удовольствие от кодирования, продолжайте ...

Тактика: решить проблему на бумаге.