Массив удалить дубликаты элементов - PullRequest
Новая
       16

Массив удалить дубликаты элементов

29 голосов
/ 28 июля 2010

У меня есть несортированный массив, каков наилучший способ удалить все дубликаты элемента, если он есть?

например: 

a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3]

поэтому после этой операции массив должен выглядеть как 

 a[1,5,2,6,8,9,10,3,4,11]

Ответы [ 13 ]

74 голосов
/ 28 июля 2010

Сверьте каждый элемент с каждым другим элементом

Наивным решением является проверка каждого элемента на предмет соответствия каждому другому элементу. Это расточительно и дает решение O (n 2 ), даже если вы идете только вперед.

Сортировка и удаление дубликатов

Лучшее решение - отсортировать массив, а затем проверить каждый элемент рядом с ним, чтобы найти дубликаты. Выберите эффективную сортировку, и это O (n log n).

Недостатком решения на основе сортировки является то, что порядок не поддерживается. Однако об этом может позаботиться дополнительный шаг. Поместите все записи (в уникальный отсортированный массив) в хеш-таблицу с доступом O (1). Затем переберите исходный массив. Для каждого элемента проверьте, находится ли он в хэш-таблице. Если это так, добавьте его к результату и удалите из хеш-таблицы. В результате вы получите результирующий массив, имеющий порядок оригинала, причем каждый элемент находится в той же позиции, что и его первое вхождение.

Линейные виды целых чисел

Если вы имеете дело с целыми числами некоторого фиксированного диапазона, вы можете добиться еще лучших результатов, используя радикальную сортировку. Если вы предполагаете, что все числа находятся в диапазоне от 0 до 1 000 000, например, вы можете выделить битовый вектор примерно 1 000 001. Для каждого элемента в исходном массиве вы устанавливаете соответствующий бит на основе его значения (например, значение 13 приводит к установке 14-го бита). Затем просмотрите исходный массив, проверьте, находится ли он в битовом векторе. Если это так, добавьте его в массив результатов и очистите этот бит от вектора битов. Это O (n) и меняет пространство на время.

Решение для хеш-таблицы

Что приводит нас к лучшему решению из всех: на самом деле этот вид отвлекает, хотя и полезен. Создайте хеш-таблицу с доступом O (1). Пройдите оригинальный список. Если его еще нет в хеш-таблице, добавьте его в массив результатов и добавьте в хеш-таблицу. Если он находится в хеш-таблице, игнорируйте его.

Это, безусловно, лучшее решение. Так зачем отдыхать? Потому что подобные проблемы связаны с адаптацией имеющихся у вас (или должны быть) знаний к проблемам и их уточнением на основе предположений, которые вы делаете в решении. Разрабатывать решение и понимать его мышление гораздо полезнее, чем извергать решение.

Кроме того, хеш-таблицы не всегда доступны. Возьмите встроенную систему или что-то, где пространство ОЧЕНЬ ограничено. Вы можете реализовать быструю сортировку в нескольких кодах операций, гораздо меньше, чем в любой хэш-таблице.

2 голосов
/ 28 июля 2010

Если вам не нужно сохранять исходный объект, вы можете зациклить его и создать новый массив уникальных значений.В C # используйте Список, чтобы получить доступ к необходимым функциям.Это не самое привлекательное или интеллектуальное решение, но оно работает.

int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5};
List<int> unique = new List<int>();

foreach (int i in numbers)
     if (!unique.Contains(i))
          unique.Add(i);

unique.Sort();
numbers = unique.ToArray();
2 голосов
/ 28 июля 2010

Это можно сделать в амортизированном O (n) с использованием набора на основе хеш-таблицы.

псевдопользователей-код: 

s := new HashSet
c := 0
for each el in a
  Add el to s.
    If el was not already in s, move (copy) el c positions left.
    If it was in s, increment c.
1 голос
/ 11 мая 2014 
    indexOutput = 1;
    outputArray[0] = arrayInt[0];
    int j;
    for (int i = 1; i < arrayInt.length; i++) {            
        j = 0;
        while ((outputArray[j] != arrayInt[i]) && j < indexOutput) {
            j++;
        }
        if(j == indexOutput){
           outputArray[indexOutput] = arrayInt[i];
           indexOutput++;
        }         
    }
1 голос
/ 28 июля 2010

Обрабатывать числа как ключи. 

for each elem in array:
if hash(elem) == 1 //duplicate
  ignore it
  next
else
  hash(elem) = 1
  add this to resulting array 
end
Если вы знаете о данных, таких как диапазон чисел, и если они конечны, вы можете инициализировать этот большой массив нулями.
0 голосов
/ 10 сентября 2017

Вы можете использовать синтаксис "in" и "not in" в python, что делает его довольно простым.

Сложность выше, чем в подходе хеширования, хотя, так как «не в» эквивалентно линейному обходу, чтобы выяснить, существует ли эта запись или нет. 

li = map(int, raw_input().split(","))
a = []
for i in li:
    if i not in a:
        a.append(i)
print a
0 голосов
/ 31 января 2017 
public class RemoveDuplicateArray {
    public static void main(String[] args) {
        int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 2, 3, 4, 9 };
        int size = arr.length;
        for (int i = 0; i < size; i++) {
            for (int j = i+1; j < size; j++) {
                if (arr[i] == arr[j]) {
                    while (j < (size) - 1) {
                        arr[j] = arr[j + 1];
                        j++;
                    }
                    size--;
                }
            }
        }
        for (int i = 0; i < size; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

}

выход - 1 2 3 4 5 6 7 9

0 голосов
/ 03 октября 2015 
Time O(n) space O(n) 

#include <iostream>
    #include<limits.h>
    using namespace std;
    void fun(int arr[],int size){

        int count=0;
        int has[100]={0};
        for(int i=0;i<size;i++){
            if(!has[arr[i]]){
               arr[count++]=arr[i];
               has[arr[i]]=1;
            }
        }
     for(int i=0;i<count;i++)
       cout<<arr[i]<<" ";
    }

    int main()
    {
        //cout << "Hello World!" << endl;
        int arr[]={4, 8, 4, 1, 1, 2, 9};
        int size=sizeof(arr)/sizeof(arr[0]);
        fun(arr,size);

        return 0;
    }
0 голосов
/ 16 декабря 2014 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class testing {
    public static void main(String[] args) {
        EligibleOffer efg = new EligibleOffer();
        efg.setCode("1234");
        efg.setName("hey");
        EligibleOffer efg1 = new EligibleOffer();
        efg1.setCode("1234");
        efg1.setName("hey1");
        EligibleOffer efg2 = new EligibleOffer();
        efg2.setCode("1235");
        efg2.setName("hey");
        EligibleOffer efg3 = new EligibleOffer();
        efg3.setCode("1235");
        efg3.setName("hey");
        EligibleOffer[] eligibleOffer = { efg, efg1,efg2 ,efg3};
        removeDupliacte(eligibleOffer);
    }

    public static EligibleOffer[] removeDupliacte(EligibleOffer[] array) {
        List list = Arrays.asList(array);
        List list1 = new ArrayList();
        int len = list.size();
        for (int i = 0; i <= len-1; i++) {
            boolean isDupliacte = false;
            EligibleOffer eOfr = (EligibleOffer) list.get(i);
            String value = eOfr.getCode().concat(eOfr.getName());
            if (list1.isEmpty()) {
                list1.add(list.get(i));
                continue;
            }
            int len1 = list1.size();
            for (int j = 0; j <= len1-1; j++) {
                EligibleOffer eOfr1 = (EligibleOffer) list1.get(j);
                String value1 = eOfr1.getCode().concat(eOfr1.getName());
                if (value.equals(value1)) {
                    isDupliacte = true;
                    break;
                }
                System.out.println(value+"\t"+value1);
            }
            if (!isDupliacte) {
                list1.add(eOfr);
            }
        }
        System.out.println(list1);
        EligibleOffer[] eligibleOffer = new EligibleOffer[list1.size()];
        list1.toArray(eligibleOffer);
        return eligibleOffer;
    }
}
0 голосов
/ 03 октября 2014

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

  public class MyArray
        {
            //data arr
            private int[] _arr;
            //field length of my arr
            private int _leght;
            //counter of duplicate
            private int countOfDup = 0;
            //property length of my arr
            public int Length
            {
                get
                {
                    return _leght;
                }
            }

            //constructor
            public MyArray(int n)
            {
                _arr = new int[n];
                _leght = 0;
            }

            // put element into array
            public void Insert(int value)
            {
                _arr[_leght] = value;
                _leght++;
            }

            //Display array
            public void Display()
            {
                for (int i = 0; i < _leght; i++) Console.Out.Write(_arr[i] + " ");
            }

            //Insertion sort for sorting array
            public void InsertSort()
            {
                int t, j;
                for (int i = 1; i < _leght; i++)
                {
                    t = _arr[i];
                    for (j = i; j > 0; )
                    {
                        if (_arr[j - 1] >= t)
                        {
                            _arr[j] = _arr[j - 1];
                            j--;
                        }
                        else break;
                    }
                    _arr[j] = t;
                }
            }

            private void _markDuplicate()
            {
                //mark duplicate Int32.MinValue
                for (int i = 0; i < _leght - 1; i++)
                {
                    if (_arr[i] == _arr[i + 1])
                    {
                        countOfDup++;
                        _arr[i] = Int32.MinValue;
                    }
                }
            }

            //remove duplicates O(N) ~ O(2N) ~ O(N + N)
            public void RemoveDups()
            {
                _markDuplicate();
                if (countOfDup == 0) return; //no duplicate
                int temp = 0;

                for (int i = 0; i < _leght; i++)
                {
                    // if duplicate remember and continue
                    if (_arr[i] == Int32.MinValue) continue;
                    else //else need move 
                    {
                        if (temp != i) _arr[temp] = _arr[i];
                        temp++;
                    }
                }
                _leght -= countOfDup;
            }
        }

И Main 

static void Main(string[] args)
{
     Random r = new Random(DateTime.Now.Millisecond);
     int i = 11;
     MyArray a = new MyArray(i);
     for (int j = 0; j < i; j++)
     {
        a.Insert(r.Next(i - 1));
     }

     a.Display();
     Console.Out.WriteLine();
     a.InsertSort();
     a.Display();
     Console.Out.WriteLine();
     a.RemoveDups();
     a.Display();

    Console.ReadKey();
}
Страница:
...