найти повторение повторяющихся чисел

Question

это мой алгоритм, который я написал с друзьями (которые в StackOverflow сайте) этот алгоритм будет найти только первый номер дубликата и возвращает .Так работу в O(n) Я хочу завершите этот алгоритм, который поможет мне получить повторяющиеся числа с их повторением. что у меня есть [1,1,3,0,5,1,5] Я хочу, чтобы этот алгоритм возвращал 2 дублирующиеся числа, которые являются 1 and 5 с их повторением, которое равно 3 and 2 соответственно. Как я могу это сделать с помощью O(n)?

1 Algorithm Duplicate(arr[1:n],n) 
2 
3 { 
4  Set s = new HashSet();i:=0; 
5  while i<a.size() do 
6  { 
7   if(!s.add(a[i)) then 
8   { 
9    return a[i]; //this is a duplicate value! 
10   break; 
11   } 
12   i++; 
13  } 
14 } 

Answer 1

Вы можете сделать это в Java:

List<Integer> num=Arrays.asList(1,1,1,2,3,3,4,5,5,5); 
    Map<Integer,Integer> countNum=new HashMap<Integer, Integer>(); 
    for(int n:num) 
    { 
     Integer nu; 
     if((nu=countNum.get(n))==null) 
     { 
      countNum.put(n,1); 
      continue; 
     } 
     countNum.put(n,nu+1); 
    } 

Вместо перебора каждый раз, чтобы получить счетчик дублировать его лучше хранить счетчик на карте.

Answer 2

1. использовать карту/Словарь структуры данных.
2. Итерации по списку.
3. Для каждого элемента в списке выполните поиск по карте. Если ключ (элемент) существует, увеличьте его значение. Если ключ не существует, вставьте ключ и начальный счетчик.

Answer 3

В данном конкретном случае речь идет не столько об алгоритме, а о структуре данных: Multiset - это как Set, за исключением того, что он не хранит только уникальные элементы, вместо этого он хранит подсчет того, как часто каждый элемент в Multiset. В основном, Set говорит вам, является ли конкретный элемент в Setна всех, в дополнение к этому Multiset также сообщает вам как часто этот конкретный пункт в Multiset.

Итак, в основном все, что вам нужно сделать, это построить Multiset от вашего Array. Вот пример в Ruby:

require 'multiset' 

print Multiset[1,1,3,0,5,1,5] 

Да, это все, что нужно. Эта печать:

#3 1 
#1 3 
#1 0 
#2 5 

Если вы хотите только фактические дубликаты, вы просто delete эти пункты с числом менее 2:

print Multiset[1,1,3,0,5,1,5].delete_with {|item, count| count < 2 } 

Это печатает только

#1 3 
#2 5 

Как @suihock упоминает , вы также можете использовать Map, что в основном означает, что вместо Multiset, заботясь о подсчете элементов для вы, вы должны сделать это сами:

m = [1,1,3,0,5,1,5].reduce(Hash.new(0)) {|map, item| map.tap { map[item] += 1 }} 
print m 
# { 1 => 3, 3 => 1, 0 => 1, 5 => 2 } 

Опять же, если вы хотите только дублированные:

print m.select {|item, count| count > 1 } 
# { 1 => 3, 5 => 2 } 

Но вы можете иметь, что проще, если вместо того чтобы считать себя, вы используете Enumerable#group_by к группе по элементы сами по себе, а затем сопоставляют группировки с их размерами.И, наконец, преобразовать обратно в Hash:

print Hash[[1,1,3,0,5,1,5].group_by(&->x{x}).map {|n, ns| [n, ns.size] }] 
# { 1 => 3, 3 => 1, 0 => 1, 5 => 2 } 

Все они имеют амортизируется наихудший шаг сложности Θ (п).