найти дубликаты в целочисленном массиве с границами

Question

Ниже приведено описание проблемы и алгоритм, который я написал. Что-нибудь нужно сделать, чтобы улучшить этот алгоритм?

Учитывая целочисленный массив неизвестного размера, содержащий только числа от 0 до 30, напишите функцию, которая возвращает целочисленный массив, содержащий все дубликаты.

int[] findDupes(int[] array) {
    int[] found = new int[30];
    int[] dupes = new int[30];
    int dupesCount = 0;
    for (int i = 0; i < array.length; i++) {
        if (found[array[i]] <= 1) {
            found[array[i]]++;              
        }else{
            continue;
        }
        if(found[array[i]] > 1){
            dupes[dupesCount++] = array[i];
            if (dupesCount == 30)
                break;
        }
    }
    if (dupesCount == 0)
        return new int[0];
    return dupes;
}

Я предполагаю, что лучший вариант для запуска этого алгоритма будет n или 30, в зависимости от того, что меньше и наихудший случай для запуска этого алгоритма - n, так как мне приходится сканировать весь массив, чтобы найти дубликаты. Есть комментарии?

Answer 1

У вас есть правильная идея, но спросите себя, что делает этот блок, точно

    if(found[array[i]] > 1){
        dupes[dupesCount++] = array[i];
        if (dupesCount == 30)
            break;
    }

, когда он срабатывает?

Пройдите свой код с паройсэмплы, включающие массив из 1000 вхождений 0.

Что именно вы возвращаете?зачем вам нужен особый случай 0.

Также время выполнения наилучшего случая будет больше 30. Какой минимальный входной сигнал останавливает его до достижения конца?

Answer 2

Нужно более точное определение проблемы. Есть только 1 или 2 вхождения целого числа? Может ли быть 0 или 3 вхождения?

Если есть только 1 или 2 вхождения целого числа, а целые числа находятся в диапазоне от 1 до 30; Я хотел бы получить BitSet и перевернуть его, когда найду целое число. Когда я закончу чтение исходного массива, все биты, которые равны 0, будут представлять целые числа, содержащие дубликаты.

Answer 3

вот модифицированная версия с вложенными комментариями.

int[] found = new int[3];
    int[] dupes = new int[3];
    int dupesCount = 0;
    for (int i = 0; i < array.length; i++) {
        if (found[array[i]] <= 1) {
            found[array[i]]++;              
        }
        if(found[array[i]] > 1){ //duplicate found
            dupes[dupesCount++] = array[i];

            // if 30 duplicate are found don't scan the array any more
            // since the distinct numbers are only 30
            if (dupesCount == 30) 
                break;
        }
    }
    if (dupesCount == 0)
        return null;
    return dupes;

Answer 4

Что-то странное:

    if (found[array[i]] <= 1)              
    }else{
        continue;//happens if found[array[i]] > 1
    }
    if(found[array[i]] > 1){//usually don't get here, because of continue

Исправлено ли продолжение, добавляющее число только один раз?Хотя это работает, код вводит в заблуждение.

Нужно ли возвращать массив длиной 30, если есть только один дубликат?

Я бы посоветовал сделать ваш код медленнее и лучше, разбивая задачи.