Найдите пересечение обоих списков и создайте новый список, который содержит элементы в соответствии с частотой - PullRequest
Новая
       16

Найдите пересечение обоих списков и создайте новый список, который содержит элементы в соответствии с частотой

0 голосов
/ 18 февраля 2020

Если у нас есть два списка: 

list1 = [1,2,1,1,2,4,1];

list2 = [1,2,1,3,2,1];

, то новый список содержит общие элементы или пересечение списков, а затем элементы добавляются с использованием счетчика частоты:

Ожидаемый результат: 

list3 = [1,1,1,2,2];

Решение, с которым я пришел, но оно не оптимизировано 

List<Integer> commonlist = new ArrayList<Integer>(list2);
    List<Integer> intersectionlist = new ArrayList<Integer>();
    commonlist.retainAll(list1);
    for (int i : commonlist) {
        int freq1 = Collections.frequency(list1, i);
        // System.out.println("list1: " + i + " -> " + freq1);
        int freq2 = Collections.frequency(list2, i);
        // System.out.println("list2: " + i + " -> " + freq2);
        if (freq1 < freq2) {
            for (int j = 1; j <= freq1; j++) {
                intersectionlist.add(i);
            }
        } else {
            for (int j = 1; j <= freq2; j++) {
                intersectionlist.add(i);
            }
        }
    }
    System.out.println(intersectionlist);

1 Ответ

0 голосов
/ 18 февраля 2020

Я попробовал подход, каждый раз, когда встречается общий элемент, мы увеличиваем карту, которая хранит частоты: 

public List<Integer> getCommon(int[] a, int[] b) {
    Map<Integer, Integer> frequencies = new HashMap<Integer, Integer>();
    List<Integer> sets = new ArrayList<Integer>();

    for (int i : a) {
        for (int j=0; j<b.length; ++j) {
            if (i == b[j]) {
                int frequency = (int) frequencies.getOrDefault((Integer) i, 0) + 1;
                frequencies.put((Integer) i, frequency);
                b[j] = -1;
                break;
            }
        }
    }

    for (Map.Entry<Integer, Integer> entry : frequencies.entrySet()) {
        int key = (int) entry.getKey();
        int value = (int) entry.getValue();
        for (int i = 0; i < value; ++i) {
            sets.add(key);
        }
    }

    return sets;
}

Результат будет [1, 1, 1, 2, 2]

...