Я получил эту проблему из интервью с Microsoft.
Учитывая массив случайных целых чисел, написать алгоритм в C, который удаляет дублировать номера и возвращать уникальные номера в оригинале массив.
Например, вход: {4, 8, 4, 1, 1, 2, 9} Выход: {4, 8, 1, 2, 9, ?, ?}
Одно из предостережений заключается в том, что ожидаемый алгоритм не должен требовать, чтобы массив сначала сортировался. И когда элемент был удален, следующие элементы также должны быть сдвинуты вперед. Во всяком случае, значение элементов в хвосте массива, где элементы были сдвинуты вперед, незначительно.
Обновление: Результат должен быть возвращен в исходном массиве, а вспомогательная структура данных (например, hashtable) не должна использоваться. Однако, я думаю, сохранение заказа не требуется.
Update2: Для тех, кто задается вопросом, почему эти непрактичные ограничения, это был вопрос интервью, и все эти ограничения обсуждаются во время процесса мышления, чтобы увидеть, как я могу придумать разные идеи.
Как насчет:
void rmdup(int *array, int length)
{
int *current , *end = array + length - 1;
for ( current = array + 1; array < end; array++, current = array + 1 )
{
while ( current <= end )
{
if ( *current == *array )
{
*current = *end--;
}
else
{
current++;
}
}
}
}
Должно быть O (n ^ 2) или меньше.
Решение, предложенное моей подругой, является разновидностью сортировки слияния. Единственная модификация заключается в том, что во время шага слияния просто игнорируйте дублирующиеся значения. Это решение было бы также O (n log n). В этом подходе удаление сортировки/дублирования объединяется вместе. Однако я не уверен, что это имеет значение.
Я разместил это раньше, но я воспроизведу его здесь, потому что это довольно круто. Он использует хэширование, создавая что-то вроде хеш-набора на месте. Это гарантировано, что O (1) в подмышечной области (рекурсия - это хвостовой вызов) и, как правило, O (N). Алгоритм выглядит следующим образом:
Это может быть показано как O (N), если в хешировании не существует патологического сценария: даже если дубликатов нет, примерно 2/3 элементов будут устранены при каждой рекурсии. Каждый уровень рекурсии равен O (n), где малый n - количество оставшихся элементов. Единственная проблема заключается в том, что на практике он медленнее, чем быстрый, когда имеется несколько дубликатов, т.е. Много столкновений. Однако, когда есть огромное количество дубликатов, это удивительно быстро.
Изменить: В текущих реализациях D hash_t - 32 бита. Все об этом алгоритме предполагает, что будет очень мало, если таковые имеются, хеш-коллизий в полном 32-битном пространстве. Однако столкновения могут часто возникать в пространстве модулей. Однако это предположение, по всей вероятности, будет справедливым для любого набора данных с разумным размером. Если ключ меньше или равен 32 битам, это может быть его собственный хеш, что означает, что столкновение в полном 32-битном пространстве невозможно. Если он больше, вы просто не можете разместить их достаточно в 32-битном адресном пространстве памяти, чтобы это было проблемой. Я предполагаю, что hash_t будет увеличено до 64 бит в 64-битных реализациях D, где наборы данных могут быть больше. Более того, если это когда-либо окажется проблемой, можно изменить хэш-функцию на каждом уровне рекурсии.
Здесь реализована реализация на языке программирования D:
void uniqueInPlace(T)(ref T[] dataIn) {
uniqueInPlaceImpl(dataIn, 0);
}
void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
if(dataIn.length - start < 2)
return;
invariant T sentinel = dataIn[start];
T[] data = dataIn[start + 1..$];
static hash_t getHash(T elem) {
static if(is(T == uint) || is(T == int)) {
return cast(hash_t) elem;
} else static if(__traits(compiles, elem.toHash)) {
return elem.toHash;
} else {
static auto ti = typeid(typeof(elem));
return ti.getHash(&elem);
}
}
for(size_t index = 0; index < data.length;) {
if(data[index] == sentinel) {
index++;
continue;
}
auto hash = getHash(data[index]) % data.length;
if(index == hash) {
index++;
continue;
}
if(data[index] == data[hash]) {
data[index] = sentinel;
index++;
continue;
}
if(data[hash] == sentinel) {
swap(data[hash], data[index]);
index++;
continue;
}
auto hashHash = getHash(data[hash]) % data.length;
if(hashHash != hash) {
swap(data[index], data[hash]);
if(hash < index)
index++;
} else {
index++;
}
}
size_t swapPos = 0;
foreach(i; 0..data.length) {
if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
swap(data[i], data[swapPos++]);
}
}
size_t sentinelPos = data.length;
for(size_t i = swapPos; i < sentinelPos;) {
if(data[i] == sentinel) {
swap(data[i], data[--sentinelPos]);
} else {
i++;
}
}
dataIn = dataIn[0..sentinelPos + start + 1];
uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}
Если вы ищете превосходную O-нотацию, сортировка массива с помощью сортировки O (n log n), то выполнение обхода O (n) может быть лучшим. Без сортировки вы смотрите на O (n ^ 2).
Изменить: если вы просто выполняете целые числа, то вы также можете сделать сортировку radix, чтобы получить O (n).
Еще одна эффективная реализация
int i, j;
/* new length of modified array */
int NewLength = 1;
for(i=1; i< Length; i++){
for(j=0; j< NewLength ; j++)
{
if(array[i] == array[j])
break;
}
/* if none of the values in index[0..j] of array is not same as array[i],
then copy the current value to corresponding new position in array */
if (j==NewLength )
array[NewLength++] = array[i];
}
В этой реализации нет необходимости сортировать массив. Также, если найден дублирующий элемент, нет необходимости переводить все элементы после этого на одну позицию.
Результатом этого кода является массив [] с размером NewLength
Здесь мы начинаем с 2-го элемента в массиве и сравниваем его со всеми элементами в массиве до этого массива. У нас есть дополнительная индексная переменная 'NewLength' для изменения входного массива. Параметр newLength инициализируется равным 0.
Элемент в массиве [1] будет сравниваться с массивом [0]. Если они разные, тогда значение в массиве [NewLength] будет изменено с помощью массива [1] и увеличится NewLength. Если они одинаковы, NewLength не будет изменен.
Итак, если у нас есть массив [1 2 1 3 1], затем
В первом проходе цикла 'j' массив [1] (2) будет сравниваться с array0, затем 2 будет записан в массив [NewLength] = array [1] поэтому массив будет [1 2], так как NewLength = 2
Во втором проходе цикла 'j' массив [2] (1) будет сравниваться с array0 и array1. Здесь, поскольку массив [2] (1) и array0 - это тот же цикл, он будет разбит здесь. поэтому массив будет [1 2], так как NewLength = 2
и т.д.
1. Используя O (1) дополнительное пространство, в O (n log n) время
Это возможно, например:
Я считаю, что партнер ejel верен, что лучший способ сделать это - это сортировка слияния на месте с упрощенным шагом слияния, и это, вероятно, является целью вопроса, если бы вы были, например. написав новую библиотечную функцию, чтобы сделать это максимально эффективно, без возможности улучшить ввод данных, и были бы случаи, когда было бы полезно сделать это без хеш-таблицы, в зависимости от вида входных данных. Но я на самом деле не проверял это.
2. Использование O (лотов) дополнительного пространства, в O (n) времени
Это работает только при наличии нескольких сомнительных допущений:
Это плохой ответ, но если у вас есть LOTS входных элементов, но это все 8-битные целые числа (или, может быть, даже 16-битные целые числа), это может быть лучшим способом.
3. O (немного) - дополнительное пространство, O (n) - время
Как # 2, но используйте хеш-таблицу.
4. Четкий способ
Если количество элементов невелико, запись соответствующего алгоритма не является полезной, если другой код быстрее писать и быстрее читать.
Eg. Пройдите через массив для каждого уникального элемента (т.е. Первый элемент, второй элемент (дубликаты первого из них были удалены) и т.д.), Удалив все одинаковые элементы. O (1) дополнительное пространство, O (n ^ 2) время.
Eg. Используйте функции библиотеки, которые это делают. эффективность зависит от того, что вы легко доступны.
Ну, это простая реализация довольно проста. Пройдите через все элементы, проверьте, есть ли дубликаты в остальных и сдвиньте остальные на них.
Это ужасно неэффективно, и вы можете ускорить его с помощью вспомогательного массива для вывода или сортировки/бинарных деревьев, но это, похоже, не разрешено.
Вы можете сделать это одним движением, если вы готовы пожертвовать памятью. Вы можете просто подсчитать, видели ли вы целое число или нет в хеш-ассоциативном массиве. Если вы уже видели число, удалите его по мере продвижения или, еще лучше, переместите числа, которые вы не видели в новый массив, избегая любых изменений в исходном массиве.
В Perl:
foreach $i (@myary) {
if(!defined $seen{$i}) {
$seen{$i} = 1;
push @newary, $i;
}
}
Если вам разрешено использовать С++, вызов std::sort, за которым следует вызов std::unique, даст вам ответ. Сложность времени - O (N log N) для сортировки и O (N) для единственного обхода.
И если С++ отключен от таблицы, нет ничего, что заставило бы эти же алгоритмы записываться в C.
Возвращаемое значение функции должно быть числом уникальных элементов, и все они хранятся в передней части массива. Без этой дополнительной информации вы даже не узнаете, есть ли дубликаты.
Каждая итерация внешнего цикла обрабатывает один элемент массива. Если он уникален, он остается в передней части массива, и если он является дубликатом, он перезаписывается последним необработанным элементом в массиве. Это решение работает в O (n ^ 2) времени.
#include <stdio.h>
#include <stdlib.h>
size_t rmdup(int *arr, size_t len)
{
size_t prev = 0;
size_t curr = 1;
size_t last = len - 1;
while (curr <= last) {
for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
if (prev == curr) {
++curr;
} else {
arr[curr] = arr[last];
--last;
}
}
return curr;
}
void print_array(int *arr, size_t len)
{
printf("{");
size_t curr = 0;
for (curr = 0; curr < len; ++curr) {
if (curr > 0) printf(", ");
printf("%d", arr[curr]);
}
printf("}");
}
int main()
{
int arr[] = {4, 8, 4, 1, 1, 2, 9};
printf("Before: ");
size_t len = sizeof (arr) / sizeof (arr[0]);
print_array(arr, len);
len = rmdup(arr, len);
printf("\nAfter: ");
print_array(arr, len);
printf("\n");
return 0;
}
Очевидно, что массив должен быть "пройден" справа налево, чтобы избежать ненужного копирования значений взад и вперед.
Если у вас есть неограниченная память, вы можете выделить бит-массив для sizeof(type-of-element-in-array) / 8 байтов, чтобы каждый бит означал, что вы уже встретили соответствующее значение или нет.
Если вы этого не сделаете, я не могу придумать ничего лучше, чем пересечение массива и сравнение каждого значения со значениями, которые следуют за ним, а затем, если будет найден дубликат, полностью удалить эти значения. Это где-то вблизи O (n ^ 2) (или O ((n ^ 2-n)/2)).
В IBM есть статья по своему близкому вопросу.
Посмотрим:
Вот версия Java.
int[] removeDuplicate(int[] input){
int arrayLen = input.length;
for(int i=0;i<arrayLen;i++){
for(int j = i+1; j< arrayLen ; j++){
if(((input[i]^input[j]) == 0)){
input[j] = 0;
}
if((input[j]==0) && j<arrayLen-1){
input[j] = input[j+1];
input[j+1] = 0;
}
}
}
return input;
}
В Java я бы решил это так. Не знаю, как записать это в C.
int length = array.length;
for (int i = 0; i < length; i++)
{
for (int j = i + 1; j < length; j++)
{
if (array[i] == array[j])
{
int k, j;
for (k = j + 1, l = j; k < length; k++, l++)
{
if (array[k] != array[i])
{
array[l] = array[k];
}
else
{
l--;
}
}
length = l;
}
}
}
Это можно сделать за один проход с помощью алгоритма O (N log N) и без дополнительного хранилища.
Перейдите от элемента a[1] к a[N]. На каждом этапе i все элементы слева от a[i] содержат отсортированную кучу элементов a[0] через a[j]. Между тем, второй индекс j, первоначально 0, отслеживает размер кучи.
Изучите a[i] и вставьте его в кучу, которая теперь занимает элементы a[0] до a[j+1]. Когда элемент вставлен, если встречается повторяющийся элемент a[k] с одинаковым значением, не вставляйте a[i] в кучу (т.е. Отбрасывайте его); иначе вставьте его в кучу, которая теперь растет на один элемент и теперь содержит от a[0] до a[j+1] и увеличивает j.
Продолжайте таким образом, увеличивая i до тех пор, пока все элементы массива не будут рассмотрены и не вставлены в кучу, которая заканчивается тем, что занимает от a[0] до a[j]. j - это индекс последнего элемента кучи, а куча содержит только уникальные значения элементов.
int algorithm(int[] a, int n)
{
int i, j;
for (j = 0, i = 1; i < n; i++)
{
// Insert a[i] into the heap a[0...j]
if (heapInsert(a, j, a[i]))
j++;
}
return j;
}
bool heapInsert(a[], int n, int val)
{
// Insert val into heap a[0...n]
...code omitted for brevity...
if (duplicate element a[k] == val)
return false;
a[k] = val;
return true;
}
Глядя на пример, это не совсем то, о чем просили, поскольку результирующий массив сохраняет исходный порядок элементов. Но если это требование ослаблено, алгоритм выше должен сделать трюк.
Как насчет следующего?
int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
for(y=0;y<count;y++)
{
if(*(temp+y)==*(array+x))
{
break;
}
}
if(y==count)
{
*(temp+count) = *(array+x);
count++;
}
}
memcpy(array, temp, sizeof(int)*len);
Я пытаюсь объявить массив temp и поместить элементы в это, прежде чем копировать все обратно в исходный массив.
После обзора проблемы, вот мой метод delphi, который может помочь
var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;
for I := 0 to C-1 do
begin
for J := I+1 to C-1 do
if A[I]=A[J] then
begin
for K := C-1 Downto J do
if A[J]<>A[k] then
begin
P:=A[K];
A[K]:=0;
A[J]:=P;
C:=K;
break;
end
else
begin
A[K]:=0;
C:=K;
end;
end;
end;
//tructate array
setlength(A,C);
end;
Следующий пример должен решить вашу проблему:
def check_dump(x):
if not x in t:
t.append(x)
return True
t=[]
output = filter(check_dump, input)
print(output)
True
Вот мое решение.
///// find duplicates in an array and remove them
void unique(int* input, int n)
{
merge_sort(input, 0, n) ;
int prev = 0 ;
for(int i = 1 ; i < n ; i++)
{
if(input[i] != input[prev])
if(prev < i-1)
input[prev++] = input[i] ;
}
}
import java.util.ArrayList;
public class C {
public static void main(String[] args) {
int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};
ArrayList<Integer> arr1 = new ArrayList<Integer>();
for(int i=0;i<arr.length-1;i++){
if(arr[i] == arr[i+1]){
arr[i] = 99999;
}
}
for(int i=0;i<arr.length;i++){
if(arr[i] != 99999){
arr1.add(arr[i]);
}
}
System.out.println(arr1);
}
}
Это наивное (N * (N-1)/2) решение. Он использует постоянное дополнительное пространство и сохраняет исходный порядок. Это похоже на решение @Byju, но не использует блоки if(){}. Он также позволяет избежать копирования элемента на себя.
#include <stdio.h>
#include <stdlib.h>
int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])
size_t undup_it(int array[], size_t len)
{
size_t src,dst;
/* an array of size=1 cannot contain duplicate values */
if (len <2) return len;
/* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
size_t cur;
for (cur=0; cur < dst; cur++ ) {
if (array[cur] == array[src]) break;
}
if (cur != dst) continue; /* found a duplicate */
/* array[src] must be new: add it to the list of non-duplicates */
if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
dst++;
}
return dst; /* number of valid alements in new array */
}
void print_it(int array[], size_t len)
{
size_t idx;
for (idx=0; idx < len; idx++) {
printf("%c %d", (idx) ? ',' :'{' , array[idx] );
}
printf("}\n" );
}
int main(void) {
size_t cnt = COUNT;
printf("Before undup:" );
print_it(numbers, cnt);
cnt = undup_it(numbers,cnt);
printf("After undup:" );
print_it(numbers, cnt);
return 0;
}
Это можно сделать за один проход в O (N) раз в количестве целых чисел на входе список и O (N) хранилище в количестве уникальных целых чисел.
Пройдите по списку спереди назад, с двумя указателями "dst" и "src" инициализируется первым элементом. Начните с пустой хеш-таблицы из числа "целых чисел". Если целое число в src отсутствует в хэше, записать его в слот на dst и приращение dst. Добавьте целое число в src к хешу, затем приращение src. Повторяйте до тех пор, пока src не завершит список ввода.
Вставьте все элементы в binary tree the disregards duplicates - O(nlog(n)). Затем извлеките все из них в массив, выполнив обход - O(n). Я предполагаю, что вам не нужно сохранять порядок.
Используйте фильтр цветения для хеширования. Это значительно сократит объем памяти.
Создайте BinarySearchTree, у которого есть сложность O (n).
В JAVA,
Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};
String value ="";
for(Integer i:arrayInteger)
{
if(!value.contains(Integer.toString(i))){
value +=Integer.toString(i)+",";
}
}
String[] arraySplitToString = value.split(",");
Integer[] arrayIntResult = new Integer[arraySplitToString.length];
for(int i = 0 ; i < arraySplitToString.length ; i++){
arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
}
Выход: {1, 2, 3, 4, 6, 7, 8, 9, 10}
надеюсь, что это поможет
Сначала вы должны создать массив check[n], где n - количество элементов массива, которое вы хотите сделать без дубликатов, и установить значение каждого элемента (массива проверки) равным 1. Использование a для цикл пересекает массив с дубликатами, скажем, его имя arr, а в for-loop пишите это:
{
if (check[arr[i]] != 1) {
arr[i] = 0;
}
else {
check[arr[i]] = 0;
}
}
При этом вы устанавливаете каждый дубликат равным нулю. Поэтому остается только пройти массив arr и напечатать все, что не равно нулю. Порядок остается и он принимает линейное время (3 * n).
Учитывая массив из n элементов, напишите алгоритм для удаления всех дубликатов из массива за время O (nlogn)
Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array
//input parameters :a[1:n], an array of n elements.
{
temp[1:n]; //an array of n elements.
temp[i]=a[i];for i=1 to n
temp[i].value=a[i]
temp[i].key=i
//based on 'value' sort the array temp.
//based on 'value' delete duplicate elements from temp.
//based on 'key' sort the array temp.//construct an array p using temp.
p[i]=temp[i]value
return p.
В других элементах сохраняется в выходном массиве с использованием "ключа". Рассмотрим, что ключ имеет длину O (n), время, затраченное на выполнение сортировки по ключу, и значение O (nlogn). Таким образом, время, затраченное на удаление всех дубликатов из массива, - O (nlogn).
это то, что у меня есть, хотя оно меняет порядок, который мы можем сортировать по восходящему или нисходящему, чтобы исправить его.
#include <stdio.h>
int main(void){
int x,n,myvar=0;
printf("Enter a number: \t");
scanf("%d",&n);
int arr[n],changedarr[n];
for(x=0;x<n;x++){
printf("Enter a number for array[%d]: ",x);
scanf("%d",&arr[x]);
}
printf("\nOriginal Number in an array\n");
for(x=0;x<n;x++){
printf("%d\t",arr[x]);
}
int i=0,j=0;
// printf("i\tj\tarr\tchanged\n");
for (int i = 0; i < n; i++)
{
// printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
for (int j = 0; j <n; j++)
{
if (i==j)
{
continue;
}
else if(arr[i]==arr[j]){
changedarr[j]=0;
}
else{
changedarr[i]=arr[i];
}
// printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
}
myvar+=1;
}
// printf("\n\nmyvar=%d\n",myvar);
int count=0;
printf("\nThe unique items:\n");
for (int i = 0; i < myvar; i++)
{
if(changedarr[i]!=0){
count+=1;
printf("%d\t",changedarr[i]);
}
}
printf("\n");
}
Было бы здорово, если бы у вас была хорошая DataStructure, которая могла бы быстро определить, содержит ли она целое число. Возможно, какое-то дерево.
DataStructure elementsSeen = new DataStructure();
int elementsRemoved = 0;
for(int i=0;i<array.Length;i++){
if(elementsSeen.Contains(array[i])
elementsRemoved++;
else
array[i-elementsRemoved] = array[i];
}
array.Length = array.Length - elementsRemoved;