Найти дублирующий элемент в массиве во времени O (n)

Мне задали этот вопрос на собеседовании, и я задавался вопросом о правильном ответе.

У вас есть массив чисел от 0 до n-1, один из чисел удаляется и заменяется числом, уже находящимся в массиве, что делает дубликат этого числа. Как мы можем обнаружить этот дубликат во времени O (n)?

Например, массив 1,2,3,4 станет 1,2,2,4.

Простое решение времени O (n ²) заключается в использовании вложенного цикла для поиска дубликата каждого элемента.

Ответы

Ответ 1

У нас есть исходный массив int A[N]; Создаем второй массив bool B[N] тоже типа bool=false. Итерируйте первый массив и установите B[A[i]]=true, если было false, иначе bing!

Ответ 2

Это можно сделать в пространстве O(n) и O(1).

(Алгоритм работает только потому, что числа являются целыми целыми числами в известном диапазоне):

За один проход через вектор вычислите сумму всех чисел и сумму квадратов всех чисел.

Вычтите сумму всех чисел из N(N-1)/2. Назовите это A.

Вычтите сумму квадратов из N(N-1)(2N-1)/6. Разделите это на A. Вызвать результат B.

Число, которое было удалено, составляет (B + A)/2, а число, которое было заменено, равно (B - A)/2.

Пример:

Вектор [0, 1, 1, 2, 3, 5]:

N = 6
Сумма вектора равна 0 + 1 + 1 + 2 + 3 + 5 = 12. N (N-1)/2 равно 15. A = 3.
Сумма квадратов равна 0 + 1 + 1 + 4 + 9 + 25 = 40. N (N-1) (2N-1)/6 равно 55. B = (55-40)/A = 5.
Число, которое было удалено, равно (5 + 3)/2 = 4.
Число, которое оно было заменено, равно (5 - 3)/2 = 1.

Почему это работает:

Сумма исходного вектора [0, ..., N-1] равна N(N-1)/2. Предположим, что значение A было удалено и заменено на B. Теперь сумма модифицированного вектора будет N(N-1)/2 + b - a. Если мы вычтем сумму модифицированного вектора из N(N-1)/2, получим a - b. Итак, A = a - b.
Аналогично, сумма квадратов исходного вектора N(N-1)(2N-1)/6. Сумма квадратов модифицированного вектора равна N(N-1)(2N-1)/6 + b² - a². Вычитая сумму квадратов модифицированного вектора из исходной суммы, получаем a² - b², что совпадает с (a+b)(a-b). Итак, если мы разделим его на a - b (т.е. A), получим B = a + b.
Теперь B + A = a + b + a - b = 2a и B - A = a + b - (a - b) = 2b.

Ответ 3

Вы можете сделать это в O (N) раз без лишнего места. Вот как работает алгоритм:

Итерацию через массив следующим образом:

Для каждого встреченного элемента установите его соответствующее значение индекса отрицательному. Например: если вы найдете [0] = 2. Получили [2] и отрицали значение.

Делая это, вы отмечаете, что это встречается. Поскольку вы знаете, что у вас не может быть отрицательных чисел, вы также знаете, что именно вы это отрицаете.
Убедитесь, что индекс, соответствующий значению, уже отмечен отрицательным, если да, вы получаете дублированный элемент. Например: если a [0] = 2, перейдите к [2] и проверьте, является ли оно отрицательным.

Допустим, у вас есть следующий массив:

int a[]  = {2,1,2,3,4};

После первого элемента ваш массив будет:

int a[] = {2,1,-2,3,4};

После второго элемента ваш массив будет:

int a[] = {2,-1,-2,3,4};

Когда вы достигнете третьего элемента, вы переходите к [2] и видите его уже отрицательный. Вы получаете дубликат.

Ответ 4

Сканирование массива 3 раза:

XOR объединить все элементы массива → A. XOR объединяет все числа от 0 до N-1 → B. Теперь A XOR B = X XOR D, где X - удаленный элемент, а D - дублирующий элемент.
Выберите любой ненулевой бит в A XOR B. XOR объединить все элементы массива, в которых установлен этот бит → A1. XOR объединяет все числа от 0 до N-1, где установлен этот бит → B1. Теперь либо A1 XOR B1 = X, либо A1 XOR B1 = D.
Сканируйте массив еще раз и попытайтесь найти A1 XOR B1. Если он найден, это дубликат элемента. Если нет, то повторяющийся элемент A XOR B XOR A1 XOR B1.

Ответ 5

Используйте HashSet, чтобы удерживать все числа, которые уже видели. Он работает в (амортизированном) времени O(1), поэтому общее значение O(N).

Ответ 6

Я предлагаю использовать BitSet. Мы знаем, что N достаточно мало для индексации массива, поэтому бит-бит будет иметь разумный размер.

Для каждого элемента массива проверьте бит, соответствующий его значению. Если он уже установлен, то есть дубликат. Если нет, установите бит.

Ответ 7

Использовать хеш-таблицу. Включение элемента в хэш-таблицу равно O (1).

Ответ 8

@rici прав насчет использования времени и пространства: "Это может быть сделано в O (n) времени и O (1) пространстве."

Однако вопрос может быть расширен до более широкого требования: нет необходимости, чтобы было только одно дублирующее число, а числа не могли быть последовательными.

OJ ставит это так здесь: (примечание 3, по-видимому, можно сузить)

Учитывая массив nums, содержащий n + 1 целых чисел, где каждое целое число находится между 1 и n (включительно), докажите, что должно существовать как минимум одно дублирующее число. Предположим, что существует только одно дублирующее число, найдите дубликат.

Примечание:

Вы не должны изменять массив (предположим, что массив только для чтения).

Вы должны использовать только постоянное, O (1) дополнительное пространство.

Сложность выполнения должна быть меньше O (n2).

В массиве есть только одно дублирующее число, но его можно повторить более одного раза.

Вопрос очень хорошо объяснен и ответил здесь Китом Шварцем, используя Алгоритм поиска циклов Floyd:

Основной трюк, который нам нужно использовать для решения этой проблемы, заключается в том, чтобы заметить, что, поскольку у нас есть массив из n элементов от 0 до n - 2, мы можем представить массив как определение функции f из множества {0, 1,..., n - 1} на себя. Эта функция определяется как f (i) = A [i]. Учитывая эту настройку, дублируемое значение соответствует паре индексов я!= J таких, что f (i) = f (j). Поэтому наша задача состоит в том, чтобы найти эту пару (i, j). Как только мы получим его, мы сможем легко найти дублируемое значение, просто выбрав f (i) = A [i].

Но как нам найти эту повторяющуюся ценность? Оказывается, это хорошо изученная проблема в информатике, называемой детектированием цикла. Общий вид проблемы заключается в следующем. Нам дана функция f. Определим последовательность x_i как

    x_0     = k       (for some k)
    x_1     = f(x_0)
    x_2     = f(f(x_0))
    ...
    x_{n+1} = f(x_n)

Предполагая, что f отображает из области в себя, эта функция будет иметь одну из трех форм. Во-первых, если область бесконечна, то последовательность может быть бесконечно длинной и не повторяющейся. Например, функция f (n) = n + 1 для целых чисел имеет это свойство - ни одно число не дублируется. Во-вторых, последовательность может быть замкнутой, что означает, что существует некоторый я так, что x_0 = x_i. В этом случае последовательность циклически проходит через некоторый фиксированный набор значений бесконечно. Наконец, последовательность может быть "rho-shaped". В этом случае последовательность выглядит примерно так:

 x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                    ^                       |
                    |                       |
                    +-----------------------+

То есть последовательность начинается с цепочки элементов, которая входит в цикл, а затем циклически продолжается бесконечно. Мы будем обозначать первый элемент цикла, который достигается в последовательности "запись" цикла.

Реализация python также можно найти здесь:

def findDuplicate(self, nums):
    # The "tortoise and hare" step.  We start at the end of the array and try
    # to find an intersection point in the cycle.
    slow = 0
    fast = 0

    # Keep advancing 'slow' by one step and 'fast' by two steps until they
    # meet inside the loop.
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    # Start up another pointer from the end of the array and march it forward
    # until it hits the pointer inside the array.
    finder = 0
    while True:
        slow   = nums[slow]
        finder = nums[finder]

        # If the two hit, the intersection index is the duplicate element.
        if slow == finder:
            return slow

Ответ 9

Одно рабочее решение:

число абзацев - целые числа

создать массив из [0.. N]

int[] counter = new int[N];

Затем повторите чтение и добавьте счетчик:

 if (counter[val] >0) {
   // duplicate
 } else {
   counter[val]++;
 }

Ответ 10

Это альтернативное решение в пространстве O(n) и O(1). Он похож на rici's. Я нахожу это немного легче понять, но на практике он будет переполняться быстрее.

Пусть X - недостающее число, а R - повторяющееся число.

Можно считать, что числа взяты из [1..n], т.е. нуль не появляется. Фактически, в то время как цикл через массив, мы можем проверить, был ли найден нуль и немедленно вернуться, если нет.

Теперь рассмотрим:

sum(A) = n (n + 1) / 2 - X + R

product(A) = n! R / X

где product(A) - произведение всех элементов в A, пропускающих нуль. У нас есть два уравнения с двумя неизвестными, из которых X и R могут быть получены алгебраически.

Изменить: по популярному запросу, здесь приведен пример:

Пусть set:

S = sum(A) - n (n + 1) / 2
P = n! / product(A)

Тогда наши уравнения становятся:

R - X = S
X = R P

который можно решить, чтобы:

R = S / (1 - P)
X = P R = P S / (1 - P)

Пример:

A = [0 1 2 2 4]

n = A.length - 1 = 4
S = (1 + 2 + 2 + 4) - 4 * 5 / 2 = -1
P = 4! / (1 * 2 * 2 * 4) = 3 / 2

R = -1 / (1 - 3/2) = -1 / -1/2 = 2
X = 3/2 * 2 = 3

Ответ 11

Вы можете действовать следующим образом:

сортируйте свой массив с помощью алгоритма сортировки по линейному времени (например, сортировка сортировки) - O (N)
сканировать отсортированный массив и останавливаться, как только два последовательных элемента равны - O (N)

Ответ 12

public class FindDuplicate {
    public static void main(String[] args) {
        // assume the array is sorted, otherwise first we have to sort it.
        // time efficiency is o(n)
        int elementData[] = new int[] { 1, 2, 3, 3, 4, 5, 6, 8, 8 };
        int count = 1;
        int element1;
        int element2;

        for (int i = 0; i < elementData.length - 1; i++) {
            element1 = elementData[i];
            element2 = elementData[count];
            count++;
            if (element1 == element2) {
                System.out.println(element2);
            }
        }
    }
}

Ответ 13

  public void duplicateNumberInArray {
    int a[] = new int[10];
    Scanner inp = new Scanner(System.in);
    for(int i=1;i<=5;i++){  
        System.out.println("enter no. ");
        a[i] = inp.nextInt();
    }
    Set<Integer> st = new HashSet<Integer>();
    Set<Integer> s = new HashSet<Integer>();
    for(int i=1;i<=5;i++){          
        if(!st.add(a[i])){
            s.add(a[i]);
        }
    }

    Iterator<Integer> itr = s.iterator();
                System.out.println("Duplicate numbers are");
    while(itr.hasNext()){
        System.out.println(itr.next());
    }
}

Прежде всего, создадим массив целых чисел, используя класс Scanner. Затем повторяя цикл через числа и проверяя, можно ли добавить число для установки (числа можно добавить для установки только тогда, когда этот конкретный номер не должен быть уже установлен, означает, что set не позволяет дублировать номер для добавления и возврата булевых vale FALSE при добавлении повторяющегося значения). Если нет. не может быть добавлено, значит, он дублируется, поэтому добавьте дублирующее число в другой набор, чтобы мы могли печатать позже. Пожалуйста, обратите внимание на то, что мы добавляем дубликат числа в набор, потому что возможно, что повторяющийся номер может повторяться несколько раз, поэтому добавьте его только один раз. В конце мы печатаем набор с использованием Iterator.

Ответ 14

//Это похоже на подход HashSet, но использует только одну структуру данных:

    int[] a = { 1, 4, 6, 7, 4, 6, 5, 22, 33, 44, 11, 5 };

    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();

    for (int i : a) {
        map.put(i, map.containsKey(i) ? (map.get(i)) + 1 : 1);
    }

    Set<Entry<Integer, Integer>> es = map.entrySet();
    Iterator<Entry<Integer, Integer>> it = es.iterator();

    while (it.hasNext()) {
        Entry<Integer, Integer> e = it.next();
        if (e.getValue() > 1) {
            System.out.println("Dupe " + e.getKey());
        }
    }

Ответ 15

Мы можем эффективно использовать hashMap:

Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int x : a)
{
    if (map.containsKey(x))  map.put(x,map.get(x)+1);
    else map.put(x,1);
}

Integer [] keys = map.keySet().toArray(new Integer[map.size()]);
for(int x : keys)
{
    if(map.get(x)!=1)
    {
        System.out.println(x+" repeats : "+map.get(x));
    }
}

Ответ 16

Эта программа основана на С#, и если вы хотите сделать эту программу с использованием другого языка программирования, вы должны сначала изменить массив в порядке возрастания и сравнить первый элемент со вторым элементом. Если он равен, то повторное число найдено. Программа

int[] array=new int[]{1,2,3,4,5,6,7,8,9,4};
Array.Sort(array);
for(int a=0;a<array.Length-1;a++)
{
  if(array[a]==array[a+1]
  {
     Console.WriteLine("This {0} element is repeated",array[a]);
   }
}
Console.WriteLine("Not repeated number in array");

Ответ 17

сортировать массив O (n ln n)

используя трюк скользящего окна для перемещения массива O (n)

Пространство равно O (1)

Arrays.sort(input);
for(int i = 0, j = 1; j < input.length ; j++, i++){
    if( input[i] == input[j]){
        System.out.println(input[i]);
        while(j < input.length && input[i] == input[j]) j++;
        i = j - 1;
    }
}

Тестовый случай int [] {1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7}

вывод 1, 2, 3, 7

Ответ 18

Этот вопрос может быть тем же вопросом, что и check whether there is a circle in the array, здесь - это одна из хороших ссылок для его решения.

Ответ 19

Пройдите через массив и проверьте знак array[abs(array[i])], если положительный сделайте его отрицательным, а если он отрицательным, напечатайте его следующим образом:

import static java.lang.Math.abs;

public class FindRepeatedNumber {

    private static void findRepeatedNumber(int arr[]) {
        int i;
        for (i = 0; i < arr.length; i++) {
            if (arr[abs(arr[i])] > 0)
                arr[abs(arr[i])] = -arr[abs(arr[i])];
            else {
                System.out.print(abs(arr[i]) + ",");
            }
        }
    }

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

Ссылка: http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

Ответ 20

Как описано,

У вас есть массив чисел от 0 до n-1, одно из чисел - удаляется и заменяется числом, уже находящимся в массиве, что делает дубликат этого номера.

Я предполагаю, что элементы в массиве отсортированы, за исключением дублированной записи. Если это сценарий, мы можем легко достичь цели, как показано ниже:

        public static void main(String[] args) {
    //int arr[] = { 0, 1, 2, 2, 3 };
    int arr[] = { 1, 2, 3, 4, 3, 6 };
    int len = arr.length;
    int iMax = arr[0];
    for (int i = 1; i < len; i++) {
        iMax = Math.max(iMax, arr[i]);
        if (arr[i] < iMax) {
            System.out.println(arr[i]);
            break;
        }else if(arr[i+1] <= iMax) {
            System.out.println(arr[i+1]);
            break;
        }
    }
}

O (n) время и O (1) пространство, пожалуйста, поделитесь своими мыслями.

Ответ 21

Эскиз моего решения:

сохранить переменную Sum, которая изначально равна нулю.
Итерации по массиву и добавление текущей записи в Sum, если она нечетна,
вычтите его, когда он четный.

В итоге вы получите значение Sum, которое равно плюс или минус удвоенное число.

Вам нужно будет исправить сумму для того, чтобы длина N массива была нечетной или четной (добавьте или вычтите N).

Ответ 22

Это можно сделать за время O (n) и пространство O (1). Без изменения входного массива

Идея похожа на поиск начального узла цикла в связанном списке.
Поддерживать два указателя: быстрый и медленный

slow = a[0]
fast = a[a[0]]

цикл до медленного! = быстро
Как только мы находим цикл (медленно == быстро)
Сброс медленного возврата к нулю

slow = 0

найти начальный узел

while(slow != fast){
    slow = a[slow];
    fast = a[fast];
}

медленный ваш дубликат.

Вот реализация Java:

class Solution {
    public int findDuplicate(int[] nums) {
        if(nums.length <= 1) return -1;
        int slow = nums[0], fast = nums[nums[0]]; //slow = head.next, fast = head.next.next
        while(slow != fast){            //check for loop
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        if(slow != fast) return -1;
        slow = 0; //reset one pointer
        while(slow != fast){ //find starting point of loop
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

Ответ 23

Вот простое решение с hashmap за O (n) времени.

#include<iostream>
#include<map>
using namespace std;

int main()
{
    int a[]={1,3,2,7,5,1,8,3,6,10};
    map<int,int> mp;
    for(int i=0;i<10;i++){

        if(mp.find(a[i]) == mp.end())
            mp.insert({a[i],1});
        else
            mp[a[i]]++;
    }

    for(auto i=mp.begin();i!=mp.end();++i){
        if(i->second > 1)
            cout<<i->first<<" ";
    }

}

Ответ 24

int a[] = {2,1,2,3,4};

int b[] = {0};

for(int i = 0; i < a.size; i++)
{

    if(a[i] == a[i+1])
    {
         //duplicate found
         //copy it to second array
        b[i] = a[i];
    }
}