Учитывая массив из n целочисленных элементов, как вы узнаете, есть ли дубликаты в массиве в O (n), без использования дополнительного пространства.
С дополнительным пространством это означает дополнительное пространство порядка O (n).
Помогает ли оператор Xor каким-либо образом.
Если дополнительной информации нет, этот вопрос кажется неразрешимым, так как это Проблема отличимости элемента, которая неразрешима с ограничения, которые вы предоставили, в требуемое время.
вы можете разрешить:
(1) больше памяти и используйте хеш-таблицу/hashset и соответствуют критериям времени O (n). [итерация массива, проверка наличия элемента в хеш-таблице, если у вас есть обманы, в противном случае - вставить элемент в таблицу и продолжить].
(2) больше времени, отсортируйте массив [O (nlogn)] и выполните критерии сублинейного пространства. [После сортировки, итерации по массиву и для каждого a[i] , a[i+1], проверьте, идентичны ли они. Если вы не нашли одинаковой пары, у вас нет обмана]
РЕДАКТИРОВАТЬ. Доказательство для этого утверждения немного длинное и нуждается в математической нотации, которая здесь не поддерживается (sidenote: нам действительно нужна поддержка tex), но идея в том, что мы моделируем нашу проблему как Алгебраическое Дерево Вычислений (справедливое предположение, когда не допускается хеширование, и постоянное пространство в распоряжении), тогда Бен или доказал в своей статье Нижние границы для деревьев алгебраических вычислений ( 1983) (опубликовано в престижном ACM), эта отличительная особенность является проблемой Omega(nlogn) по этой модели. Любив показал, что тот же вывод применяется и при ограничении себя целыми числами в 1991 году: Нижняя граница для
проблема отличимости элемента целочисленного элемента, но в этих статьях делается вывод, что в модели алгебраического дерева вычислений. Задача Integer Distinctness - проблема Omega (nlogn).
На месте алгоритм сортировки по рациям
В зависимости от того, что вы на самом деле считаете временной сложностью сортировки Radix, это решение - время O (N), хотя мое личное мнение не так. Я думаю, что если вы не сделаете предположение о линейном времени для целочисленной сортировки, то проблема неразрешима.
Из-за того, что сортировка на месте, требуется только O (1) дополнительное хранилище.
Код - это все С++ 11
template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
if (zerosEnd+1 >= onesBegin-1 || mask == 0)
return;
int zerosEnd2 = zerosEnd;
int onesBegin2 = onesBegin;
while(zerosEnd2+1 <= onesBegin2-1)
{
// swap ones to the right
if ((myArray[zerosEnd2+1] & mask) != 0)
{
std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
--onesBegin2;
}
else
++zerosEnd2;
}
mask >>= 1;
//recurse on lhs
RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}
template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
int zerosEnd = -1;
int onesBegin = static_cast<int>(myArray.size());
T mask = static_cast<T>(1) << sizeof(T)*8-1;
while(zerosEnd+1 <= onesBegin-1)
{
if ( (myArray[zerosEnd+1] & mask) != 0)
{
std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
--onesBegin;
}
else
++zerosEnd;
}
mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
//recurse on lhs
RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));
// swap negatives to the front
auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
if (*iterSmallest < 0)
{
std::reverse(myArray.begin(), myArray.end());
iterSmallest = std::min_element(myArray.begin(), myArray.end());
std::reverse(myArray.begin(), iterSmallest+1);
std::reverse(iterSmallest+1, myArray.end());
}
}
for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
{
if (myArray[i] == myArray[j])
{
std::cout << "Found duplicate element " << myArray[i];
}
}
#include <iostream>
#include <string>
#include <vector>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <type_traits>
using namespace std;
#define N 10
template <typename T>
void PrintArray(const std::vector<T>& myArray)
{
for (auto&& element : myArray)
{
std::cout << element << std::endl;
}
}
template<typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void RecurseOnRadixSort(std::vector<T>& myArray, T mask, int zerosEnd, int onesBegin)
{
if (zerosEnd+1 >= onesBegin-1 || mask == 0)
return;
int zerosEnd2 = zerosEnd;
int onesBegin2 = onesBegin;
while(zerosEnd2+1 <= onesBegin2-1)
{
// swap ones to the right
if ((myArray[zerosEnd2+1] & mask) != 0)
{
std::swap(myArray[zerosEnd2+1], myArray[onesBegin2-1]);
--onesBegin2;
}
else
++zerosEnd2;
}
mask >>= 1;
//recurse on lhs
RecurseOnRadixSort(myArray, mask, zerosEnd, zerosEnd2+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin2-1, onesBegin);
}
template <typename T, typename std::enable_if<std::is_integral<T>::value>::type* = nullptr>
void InPlaceRadixSort(std::vector<T>& myArray)
{
int zerosEnd = -1;
int onesBegin = static_cast<int>(myArray.size());
T mask = static_cast<T>(1) << sizeof(T)*8-1;
while(zerosEnd+1 <= onesBegin-1)
{
if ( (myArray[zerosEnd+1] & mask) != 0)
{
std::swap(myArray[zerosEnd+1], myArray[onesBegin-1]);
--onesBegin;
}
else
++zerosEnd;
}
mask = static_cast<T>(1) << sizeof(T)*8-2; // need to reassign in case of signed datatype
//recurse on lhs
RecurseOnRadixSort(myArray, mask, -1, zerosEnd+1);
//recurse on rhs
RecurseOnRadixSort(myArray, mask, onesBegin-1, static_cast<int>(myArray.size()));
// swap negatives to the front
auto iterSmallest = std::min_element(myArray.begin(), myArray.end());
if (*iterSmallest < 0)
{
std::reverse(myArray.begin(), myArray.end());
iterSmallest = std::min_element(myArray.begin(), myArray.end());
std::reverse(myArray.begin(), iterSmallest+1);
std::reverse(iterSmallest+1, myArray.end());
}
}
int main() {
srand(time(NULL));
std::vector<int> myArray(N);
for (size_t i=0;i<myArray.size();++i)
{
myArray[i] = rand() % 100 * (rand() % 2 == 1?-1:1);
}
std::cout << "Vector before radix sort: " << std::endl;
PrintArray(myArray);
InPlaceRadixSort(myArray);
std::cout << "Vector after radix sort: " << std::endl;
PrintArray(myArray);
for (size_t i=0, j=1; j<myArray.size(); ++i,++j)
{
if (myArray[i] == myArray[j])
{
std::cout << "Found duplicate element " << myArray[i];
}
}
return 0;
}
Здесь интересное решение для этой проблемы с одним ограничением, что элементы должны находиться в диапазоне от 0 до n-2 (включительно), где n равно количество элементов.
Это работает в O (n) времени с сложностью пространства O (1).
Вот решение с использованием времени O (n) и использование пространства O (1)!
Traverse the array. Do following for every index i of A[].
{
check for sign of A[abs(A[i])] ;
if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
Кредиты: метод 5 Geek for Geeks
В общем случае эта проблема, похоже, не имеет решения из-за сильных ограничений сложности и неограниченного ввода.
Понятно, что вам нужно хотя бы N шагов, чтобы даже просмотреть все входные данные. Поэтому он не может быть быстрее, чем O(n).
Теперь, чтобы определить все возможные дубликаты, у вас есть разные возможности:
O(n^2) времяO(n log n) времени. Википедия имеет довольно длинную запись с большим количеством источников. Таким образом, вы никогда не сможете получить нужное время так. (сравнительная таблица известных алгоритмов сортировки)O(n), но эта бухгалтерия должна быть где-то сохранена. В противном случае вы просто "забудете", какие номера вы уже видели. К сожалению, бухгалтерия потребует больше места, если ваш ввод увеличивается, потому что у вас так много разных номеров, чтобы помнить. Таким образом, невозможно иметь один и тот же фиксированный объем памяти и сравнивать произвольно длинные входные последовательности. Поэтому вам придется нарушать постоянное пространство O(1).Как указывает @Atishay в своем ответе, может быть решение, если у вас очень ограниченный ввод. Здесь требуется, чтобы у вас был массив размера n, а возможные значения находятся только в диапазоне [0,n-2]. Это требование гарантирует, что там ДОЛЖНО быть дубликат, потому что в массиве меньше значений, чем элементов массива. Благодаря этим знаниям и очень конкретному диапазону значений вы можете это сделать. Но это использует очень узкие предположения и не решает общую проблему, указанную в вопросе.
Как поясняется в комментариях, существует доказанная нижняя граница временной сложности алгоритмов сортировки на основе сравнения. Для справки см. Здесь:
Это решение основано на том, которое удаляет дубликаты из массива @dsimcha, как можно найти здесь.
Он выполняет алгоритм замены на месте, с хэшами значений, используемыми для замены позиций. Обратите внимание, что это до некоторой степени уничтожает исходный контент массива. Но в вопросе ОП не было требований, которые запрещали это.
public static class DupFinder
{
public static bool HasDups(int[] array, ref int nEvals)
{
nEvals = 0;
return DupFinder.FindInPlace(array, 0, ref nEvals);
}
private static bool FindInPlace(int[] array, int start, ref int nEvals)
{
if (array.Length - start < 2)
return false;
var sentinel = array[start];
var offset = start + 1;
var len = array.Length - offset;
for (var ndx = 0; ndx < len; nEvals++)
{
var cur = array[offset + ndx];
if (cur == sentinel)
{
ndx++;
continue;
}
var hash = cur % len;
if (ndx == hash)
{
ndx++;
continue;
}
var at_hash = array[offset + hash];
if (cur == at_hash)
{
array[offset + ndx] = sentinel;
ndx++;
continue;
}
if (at_hash == sentinel)
{
Swap(array, offset, ndx, hash);
ndx++;
continue;
}
var hash_hash = at_hash % len;
if (hash_hash != hash)
{
Swap(array, offset, ndx, hash);
if (hash < ndx)
ndx++;
}
else
{
ndx++;
}
}
var swapPos = 0;
for (var i = 0; i < len; i++, nEvals++)
{
var cur = array[offset + i];
if (cur != sentinel && i == (cur % len))
Swap(array, offset, i, swapPos++);
}
for (var i = swapPos; i < len; nEvals++)
{
var cur = array[offset + i];
if (cur == sentinel)
return true; // got dups.
else
i++;
}
// Let assume C# supports tail recursion ;-)
// Then => look ma, O(1) extra storage space.
return FindInPlace(array, offset + swapPos, ref nEvals);
}
private static void Swap(int[] array, int offset, int first, int second)
{
var tmp = array[offset + first];
array[offset + first] = array[offset + second];
array[offset + second] = tmp;
}
}
Таким образом, если мы предположим на мгновение, что С# поддерживает рекурсию хвоста, и мы не учитываем используемые фреймы стека как дополнительное пространство, у него есть требования к пространству O (1).
Автор упоминает, что это сложность времени O (N). Тест (ограниченный) (в отличие от анализа сложности вычислений), который я выполнил, указывает, что он ближе к O (N log N).
Array Size Dup Position #Evals
12 7 26
12 - 35
100,000 80,000 279,997
100,000 - 453,441
реализация с использованием единственного int в качестве временной переменной.. это использование битовых векторов /
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - ‘a’;
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
или моя предыдущая реализация O (n ^ 2) без использования любой временной переменной
public static bool isDuplicate(char[] str) {
if (str == null) return false;
int len = str.length;
if (len < 2) return false;
for (int i = 1; i < len; ++i) {
for (int j = 0; j < len; ++j) {
if (str[i] == str[j]) return true;
}
}
return false;
}
Bloom filter - это эффективный размер пространства с настраиваемой ложной позитивной скоростью. Фальшивая положительная возможность означает, что вам нужно вернуться назад и проверить реальный дубликат, когда вы получаете удар от BF, вводя N ^ 2-член, но коэффициент равен ~ exp (- (дополнительное пространство, используемое для фильтра)). Это создает интересное пространство против времени компромиссов.
У меня нет доказательства, вопрос, который, как представляется, неразрешимый, но в целом "здесь интересное пространство компромиссов" является хорошим ответом на неразрешимую проблему.
Чистый пример для определения дубликатов с помощью O (n) по времени и O (1) пробелом:
public class DuplicateDetermineAlgorithm {
public static boolean isContainsDuplicate(int[] array) {
if (array == null) {
throw new IllegalArgumentException("Input array can not be null");
}
if (array.length < 2) {
return false;
}
for (int i = 0; i < array.length; i++) {
int pointer = convertToPositive(array[i]) - 1;
if (array[pointer] > 0) {
array[pointer] = changeSign(array[pointer]);
} else {
return true;
}
}
return false;
}
private static int convertToPositive(int value) {
return value < 0 ? changeSign(value) : value;
}
private static int changeSign(int value) {
return -1 * value;
}
}
public static void getDuplicatesElements (Integer arr[]){
//Status array to track the elements if they are already considered
boolean status[] = new boolean [arr.length];
//Flag to mark the element found its duplicate
boolean dupFlag = false;
//Output string
String output = "";
//Count of duplicate elements found
int count = 0;
//Initialize status array with all false i.e. no duplicates
for (int i = 0; i < arr.length; i++)
{
status[i] = false;
}
//first loop to check every element
for (int i = 0; i < arr.length - 1; i++)
{
//Initialize every element to no duplicate
dupFlag = false;
//Check if this element is not already found duplicate, if not, check now.
if (!status[i]){
for (int j = i+1; j < arr.length; j++){
if (arr[i] == arr[j]){
dupFlag = true;
status[j] = true;
}
}
}
if (dupFlag){
output = output + " " + arr[i];
count++;
}
}
System.out.println("Duplicate elements: " + output );
System.out.println("Count: " + count );
}
У меня нет ответа, но мои мысли слишком обширны для комментария. Кроме того, я хотел записать их, поэтому три часа, которые я трачу, думая о решении, не теряют впустую. Я надеюсь дать вам другую точку зрения, но если вам не нравится тратить свое время, не читайте дальше. Или просто проголосовать за этот ответ, стоит:)
Чтобы запустить наше визуальное мышление, дайте пример массиву: 50 100 150 -2 -1 0 1 2 3 4. Как вы, безусловно, можете сказать, у него нет дубликатов, поэтому наш алгоритм должен выводить FALSE. Кроме того, длина 10.
Пусть теперь игнорирует дополнительное ограничение памяти (на самом деле это сильно нарушает его, предполагая, что мы можем иметь O(\inf) дополнительную память:) и сохранять в вымышленном бесконечном массиве (он также вдвойне бесконечен, поскольку он позволяет отрицать индексы тоже) подсчеты для каждого целого. Для нашего ввода этот массив будет выглядеть следующим образом:
...000001111111000...00100...00100...001000000...
^ ^ ^
[index -2] [index 50] [index 150]
Если какой-либо из элементов массива больше, чем 1, то мы имеем дубликат, и алгоритм должен возвращать TRUE.
Предположим, что мы имеем карту f(x):-inf..inf -> 0..N, которая может сжимать наш бесконечный массив до массива размера N и, кроме того, делать это в O (N) времени. Это то, что идеально делает хэширование. Обратите внимание, что мы не заботимся о поддержании порядка массива, поскольку нам все равно, есть ли у него элементы, которые выше 1. Таким образом, мы можем объединить эти два шага и устранить необходимость в inifinite памяти - yay! Мы все еще используем дополнительную память O (N) (на самом деле, точно количество N), чтобы сохранить значения count. Следующий шаг избавится от этого.
Прежде чем я объясню этот шаг, обратите внимание, что нам действительно не нужно хранить какие-либо подсчеты больше 1. В первый раз мы хотим увеличить счетчик, и мы заметили, что оно уже имеет значение 1, мы знаем, что мы нашли дубликат! Таким образом, достаточно 1 бит памяти на счетчик. Это уменьшает требуемую память до O (lg (N)), но на самом деле нас это не волнует, поскольку это недостаточно. Важная часть состоит в том, что достаточно 1 бит памяти на счетчик.
Теперь мы будем использовать тот факт, что мы можем изменить наш входной массив. Мы переходим через массив и xor все элементы со значением первого элемента. Если результат меньше, чем значение перед операцией, мы меняем его на этот результат. Мы также сохраняем первый элемент отдельно как sw при дополнительной стоимости памяти O (1).
Теперь мы можем использовать сохраненный первый элемент sw и преобразованный массив для кодирования в подсчетах с этапа подсчета (шаги A + B) следующим образом: рассматривая элемент с индексом k A, если A[f(A[k])] < A[f(A[k])] xor sw, то счетчик zero, что означает, что рассматриваемый нами элемент - A[k] - ранее не был замечен, поэтому мы меняем A[f(A[k])] на A[f(A[k])] xor sw. Если в противном случае A[f(A[k])] > A[f(A[k])] xor sw, то счетчик one, что означает, что рассматриваемый нами элемент - A[k] - уже был замечен раньше, поэтому он является дубликатом.
Предполагая отображение:
f(-2 xr 50) -> 0
f(-1 xr 50) -> 1
f(0) -> 2
f(1) -> 3
f(2) -> 4
f(3) -> 5
f(4) -> 6
f(86) -> 7
f(150) -> 8
f(1337) -> 9
и после выполнения шагов в следующем порядке: step c; step a+b входной массив выглядит следующим образом:
50(0) 100(86) 150(164) -2(-2 xr 50) -1(-1 xr 50) 0(50) 1(51) 2(48) 3(49) 4(54) [intermediate state, not stored in memory]
0 86 150 -2 xr 50 -1 xr 50 0 1 2 3 4 [state after step c]
0 86 *164* -2 xr 50 -1 xr 50 0 1 2 3 4 [counted element 0]
0 86 164 -2 xr 50 -1 xr 50 0 1 *48* 3 4 [counted element 1]
0 86 164 -2 xr 50 -1 xr 50 0 1 48 *49* 4 [counted element 2]
*50* 86 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 3]
50 *100* 164 -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 4]
50 100 !164! -2 xr 50 -1 xr 50 0 1 48 49 4 [counted element 5]
Пытаясь подсчитать элемент с индексом 5, который равен 0, мы видим, что в массиве уже был 0! (потому что A[f(A[5])] 164, который больше, чем 164 xr 50). Таким образом, мы выводим TRUE, и алгоритм заканчивается.
Если нам не разрешено достаточно memory x time, мы обязательно что-то забудем и допустим ошибку.
К сожалению, у нас нет идеальной хэш-функции, и мы не можем просто создать память из воздуха, поэтому традиционный подход не будет работать под требуемыми ограничениями. Алгоритм, на который указывает ответ, указанный в пункте OP, может быть изменен таким образом, чтобы он позволял использовать числа, которые интерпретировались как массивы-индексы, выпадал за пределы массива, учитывая совершенную хеш-функцию. Но даже тогда его нужно изобрести, как использовать его для обнаружения дублирования, вместо того, чтобы найти один защищенный, чтобы существовать...
В любом случае, интересная проблема.
import java.util.HashSet;
import java.util.Set;
public class FindDups {
public static void main(String[] args) {
int a[]={1,2,3,3,4};
Set<Integer> s=new HashSet<Integer>();
for(int i=0;i<a.length;i++)
{
if(!s.add(a[i]))
System.out.println("at index"+ i+" "+a[i]+"is duplicate");
}
for(int i:s)
{
System.out.println(i);
}
}
}