Алгоритм для удаления уникальных элементов из массива и элементов печати в исходном порядке

Question

Существует один вопрос, который прослушивает меня, и каким-то образом я не могу понять, что с ним делать. Предположим, что задан массив {9,1,2,4,1,2,2}. Уникальными элементами массива являются 9 и 4. Выходной массив должен быть {1,2,1,2,2}. Моя идея сохранить заказ и найти дубликаты - использовать LinkedHashMap, который будет содержать записи и количество записей.

Проблема заключается в поддержании порядка элементов. Как только я поместил записи в hashMap, порядок исчезнет.

Answer 1

Я хотел бы сделать это следующим образом:

1. создать

   счета HashMap = новый HashMap();

2. итерацию вашего массива хранения массива значения как ключ и подсчета значения в качестве значения в HashMap

3. перебирать массив во второй раз и удалить значение из массива, если рассчитывать на ключ один ,

Answer 2

Нет ничего, что заставило бы массив исчезнуть. Просто перебирайте массив, проверяя, больше ли значение на карте.

Answer 3

Таким образом, простой способ сделать это - сначала подсчитать количество каждого элемента (может быть сделано в O(n)), выполнить итерацию по счетчику и поместить все элементы с count = 1 в набор (также в O(n)).

Теперь запустите исходный список и распечатайте все элементы, которые не входят в ваш комплект (также O(n)). Таким образом, решение будет работать в O(n) времени и пространства.

А вот 2 решения линия в Python:

from collections import Counter 
arr = [9,1,2,4,1,2,2] 

unique = {k for k, v in Counter(arr).iteritems() if v == 1} 
print [i for i in arr if i not in unique] 

Answer 4

Просто посчитайте элементы и проверить, если общее количество текущего элемента больше, чем один.

пример кода (C++ 11):

#include <iostream> 
#include <unordered_map> 
#include <vector> 

int main() { 
    std::vector<int> to_split = {9, 1, 2, 4, 1, 2, 2}; 

    std::vector<int> unique, not_unique; 
    std::unordered_map<int, int> counter; 
    for (int elem : to_split) { 
    ++counter[elem]; 
    } 
    for (int elem : to_split) { 
    if (counter[elem] > 1) { 
     not_unique.push_back(elem); 
    } else { 
     unique.push_back(elem); 
    } 
    } 

    std::cout << "Unique: " << std::endl; 
    for (int elem : unique) { 
    std::cout << elem << " "; 
    } 
    std::cout << std::endl; 
    std::cout << "Not unique:" << std::endl; 
    for (int elem : not_unique) { 
    std::cout << elem << " "; 
    } 
    std::cout << std::endl; 
    return 0; 
} 

Выход:

Unique: 
9 4 
Not unique: 
1 2 1 2 2 

Answer 5

Просто мозговой штурм немного, но я как-то надо думать о том, как алгоритм сортировки неустойчив может быть стабильным : украсить, сортировать, undecorate.

Учитывая ваш список входных данных, вы перебираете его, добавляя позицию элемента к списку на карте.

for (i = 0; i < length; i++) { 
    value = list[i] 
    map[value].append(i) 
} 

Затем удалите все элементы со счетом 1 и восстановить список (который вы можете сделать, потому что у вас есть индексы в карте).

Думая об этом дальше: почему бы просто не сделать 1 цикл подсчета, а затем еще один цикл для создания отфильтрованного списка? Вероятно, даже лучшая производительность, думаю, O(n). (1 итерация делать подсчеты, 1 итерация заново построить новый список)

Answer 6

Подобный подход fedekau «s, но не считая:

int[]numbers = {9,1,2,4,1,2,2}; 
int guessedDistinct = (int)(2 * Math.sqrt(numbers.length)); 
final Map<Number, Boolean> 
    seenBefore = new HashMap<>(guessedDistinct); 
for (int i : numbers) 
    seenBefore.put(i, seenBefore.containsKey(i)); 
int[] out = Arrays.stream(numbers) 
    .filter(i -> seenBefore.getOrDefault(i, false)) 
    .toArray(); 
System.out.println(Arrays.toString(out)); 

(или попытаться избежать "найти я дважды" в наполнении seenBefore:

for (int i : numbers) 
    seenBefore.compute(i, (k, seen) -> null != seen);