Мне задали этот вопрос на собеседовании, и я задавался вопросом о правильном ответе.
У вас есть массив чисел от 0 до n-1, один из чисел удаляется и заменяется числом, уже находящимся в массиве, что делает дубликат этого числа. Как мы можем обнаружить этот дубликат во времени O (n)?
Например, массив 1,2,3,4 станет 1,2,2,4.
Простое решение времени O (n 2) заключается в использовании вложенного цикла для поиска дубликата каждого элемента.
У нас есть исходный массив int A[N]; Создаем второй массив bool B[N] тоже типа bool=false. Итерируйте первый массив и установите B[A[i]]=true, если было false, иначе bing!
Это можно сделать в пространстве 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 + b2 - a2. Вычитая сумму квадратов модифицированного вектора из исходной суммы, получаем a2 - b2, что совпадает с (a+b)(a-b). Итак, если мы разделим его на a - b (т.е. A), получим B = a + b.
Теперь B + A = a + b + a - b = 2a и B - A = a + b - (a - b) = 2b.
Вы можете сделать это в 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] и видите его уже отрицательный. Вы получаете дубликат.
Сканирование массива 3 раза:
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.Используйте HashSet, чтобы удерживать все числа, которые уже видели. Он работает в (амортизированном) времени O(1), поэтому общее значение O(N).
Я предлагаю использовать BitSet. Мы знаем, что N достаточно мало для индексации массива, поэтому бит-бит будет иметь разумный размер.
Для каждого элемента массива проверьте бит, соответствующий его значению. Если он уже установлен, то есть дубликат. Если нет, установите бит.
Использовать хеш-таблицу. Включение элемента в хэш-таблицу равно O (1).
@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
Одно рабочее решение:
число абзацев - целые числа
создать массив из [0.. N]
int[] counter = new int[N];
Затем повторите чтение и добавьте счетчик:
if (counter[val] >0) {
// duplicate
} else {
counter[val]++;
}
Это альтернативное решение в пространстве 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
Вы можете действовать следующим образом:
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());
}
}
Прежде всего, создадим массив целых чисел, используя класс Scanner. Затем повторяя цикл через числа и проверяя, можно ли добавить число для установки (числа можно добавить для установки только тогда, когда этот конкретный номер не должен быть уже установлен, означает, что set не позволяет дублировать номер для добавления и возврата булевых vale FALSE при добавлении повторяющегося значения). Если нет. не может быть добавлено, значит, он дублируется, поэтому добавьте дублирующее число в другой набор, чтобы мы могли печатать позже. Пожалуйста, обратите внимание на то, что мы добавляем дубликат числа в набор, потому что возможно, что повторяющийся номер может повторяться несколько раз, поэтому добавьте его только один раз. В конце мы печатаем набор с использованием Iterator.
//Это похоже на подход 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());
}
}
Мы можем эффективно использовать 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));
}
}
Эта программа основана на С#, и если вы хотите сделать эту программу с использованием другого языка программирования, вы должны сначала изменить массив в порядке возрастания и сравнить первый элемент со вторым элементом. Если он равен, то повторное число найдено. Программа
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");
используя трюк скользящего окна для перемещения массива 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
Этот вопрос может быть тем же вопросом, что и check whether there is a circle in the array, здесь - это одна из хороших ссылок для его решения.
Пройдите через массив и проверьте знак 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/
Как описано,
У вас есть массив чисел от 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;
}
}
}
Эскиз моего решения:
В итоге вы получите значение Sum, которое равно плюс или минус удвоенное число.
Вам нужно будет исправить сумму для того, чтобы длина N массива была нечетной или четной (добавьте или вычтите N).
Это можно сделать за время 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;
}
}
Вот простое решение с 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<<" ";
}
}
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];
}
}