Как описано,

у Вас есть массив чисел от 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) пространство; совместно используйте свои мысли.

Пересечение через массив и проверку знак 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/

1. сортируют массив O (n ln n)

2. использование приема раздвижного окна для пересечения массива 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;
       }
   }
   

, интервал Теста [] {1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7}

произвел 1, 2, 3, 7

Эта программа основана на c# и если Вы хотите сделать эту программу с помощью другого языка программирования, необходимо во-первых изменить массив в акцентировании порядка и сравнить первый элемент со вторым элементом. Если это равно затем повторенное найденное число. Программа

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");

Мы можем сделать использование 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));
    }
}

//Это подобно подходу 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());
        }
    }

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

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

, В первую очередь, создание массива целого числа с помощью класса Сканера. Затем выполняя итерации цикла через числа и проверяя, может ли число быть добавлено для установки (Числа могут быть добавлены для установки только, когда то конкретное число уже не должно быть в наборе, набор средств не позволяет дубликат нет. добавить и возвратить булев FALSE долины на добавляющем дублирующемся значении).If нет. не может быть добавлен означает, что это - дубликат, так добавьте, что дублирующееся число в другой набор, так, чтобы мы могли распечатать позже. Отметьте onething, что мы добавляем дублирующееся число в набор, потому что могло бы быть возможно, что дублирующееся число могло бы несколько раз повторяться, следовательно добавьте его только однажды. Наконец мы печатаем набор с помощью Итератора.

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

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

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

предполагают, что число является целыми числами

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

int[] counter = new int[N];

Затем выполняют итерации чтения и увеличивают счетчик:

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

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

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

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

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

Примечание:

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

вопрос очень хорошо объяснен и ответил здесь Keith Schwarz, с помощью нахождение цикла Floyd алгоритм:

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

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

    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. В этом случае, циклы последовательности через некоторое фиксированное множество значений неограниченно долго. Наконец, последовательность могла быть, "имеющей форму ро". В этом случае последовательность выглядит примерно так:

 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

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

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

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

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

Просканируйте массив 3 раза:

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

Можно сделать это в O (N) время без любого дополнительного пространства. Вот то, как алгоритм работает:

Выполняют итерации через массив следующим образом:

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

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

2. Проверка, если индекс, соответствующий значению, уже отмечается отрицательный, если да Вы получаете дублированный элемент. Например: если [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] и уже видите его отрицательный. Вы получаете дубликат.

Это может быть сделано в 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]:

• Н = 6

• Сумма вектора 0 + 1 + 1 + 2 + 3 + 5 = 12. N (N-1)/2 равняется 15. = 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 было удалено и заменено [1 113]. Теперь сумма измененного вектора будет N(N-1)/2 + b - a. Если мы вычитаем сумму измененного вектора от [1 115], мы добираемся a - b. Так A = a - b.

• Точно так же сумма квадратов исходного вектора N(N-1)(2N-1)/6. Сумма квадратов измененного вектора N(N-1)(2N-1)/6 + b2 - a2. Вычитание суммы квадратов измененного вектора от исходной суммы дает a2 - b2, который совпадает с (a+b)(a-b). Таким образом, если мы делим его на [1 122] (т.е. A), мы добираемся B = a + b.

• Теперь B + A = a + b + a - b = 2a и B - A = a + b - (a - b) = 2b.

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

1. сортируют Ваш массив при помощи Линейно-разового алгоритма сортировки (например, Подсчет вида) - O (N)
2. сканируют сортированный массив и остановку, как только два последовательных элемента равны - O (N)