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

Question

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

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

В данном конкретном случае речь идет не столько об алгоритме, сколько о структуре данных: 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 }

Все из них имеют амортизированную сложность шага наихудшего случая, равную Θ (n).

Answer 3

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