найти 3 или более равных объектов в массиве?

Question

Я наткнулся на проблему, может, кто-нибудь подскажет, как ее решить?

Итак, давайте предположим, что у меня есть массив объектов (мы можем предположить, что они списки в списке),так что-то вроде этого:

{ {1,2}, {2}, {1,2}, {3,4,5}, {1,2} }

Элементы в объекте появляются только один раз (например, нет дубликатов, таких как {2,2,4}). Прежде чем я думал, мне понадобятся только два равных объекта из списка объектов и двойной циклхорошо справился с задачей, но теперь мне нужно больше, и перебор массива стал действительно болезненным. Итак, как мне найти индексы {1,2} без создания уродливого метода с циклом тройной четверки и т. д.?

Спасибо

Answer 1

Простой способ - использовать карту, где ключом является объект, а значением является целое число для счетчика. Таким образом, вы можете найти это быстрее. O (nlogn) или O (kn) для хэш-карты без коллизий.

Псевдокод (не помню точные сигнатуры методов, но вы поняли):

for (object o : myObjs)
{
    int num = 0;
    if (map.containsKey(o)) {
        map.put(o, map.get(o) + 1);
        num = map.get(o);
    } else {
        map.put(o, 1);
        num = 1;
    }
    if (num == 3)
        System.out.println("Object " + o + " has 3 members in set");
}

Answer 2

Основываясь на ответе Иисуса Рамоса, основная идея состоит в том, чтобы выполнять итерацию по каждому подсписку, отслеживая, сколько раз вы видите содержащийся элемент.-списки, это может быть даже лучший выбор, чем двойная петля, просто чтобы найти дубликаты.Компромисс - это дополнительная память для счетчиков событий.

Answer 3

Вы можете отсортировать массив, используя практически любую реализацию компаратора, которая вам нравится, при условии, что он сообщает, что логически равные объекты равны. (Ну, это также должно учитывать транзитивное свойство больше чем и меньше чем.) Тогда легко использовать линейное сканирование через отсортированный массив, чтобы найти прогоны 3 или больше.