Попытка решить Топ K Частых Элементов, используя LinkedList - PullRequest
Новая
       5

Попытка решить Топ K Частых Элементов, используя LinkedList

0 голосов
/ 27 сентября 2018

Я пытаюсь решить LeetCode # 347.Лучшие K Частых Элементов .Я знаю несколько подходов к этой проблеме, но я пытаюсь сделать это следующим образом.

1) Возьмите входной массив, например: [1,1,1,2,2,3]

2) Создайте карту целочисленной -> частоты ее появления, т.е.{[1, 3], [2, 2], [3, 1]}

3) Создайте LinkedList с узлами, которые содержат пары целое число -> частота, и вставьте элементы в этот LinkedList в порядке возрастаниячастота, т.е.head -> [1,3] -> [2,2] -> [3,1] -> null

4) Вывести первые k значений элементов этого LinkedList, т.е.[1, 2]

Что теоретически должно дать мне правильный ответ.

Я использую следующую реализацию: 

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        /*  input: [1,1,1,2,2,3], 2
            result: [1,3]
            expected: [1,2]
        */

        //stores integer->frequency pairs
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        Node sortedList = null; //head node of list

        List<Integer> res = new ArrayList<Integer>(); //result array

        //populate map with integer->frequency pairs
        for(int i : nums) {
            if(map.containsKey(i)) {
                map.put(i, map.get(i)+1);
            } else {
                map.put(i, 1);
            }
        }

        //System.out.println(map);

        //go through map
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {

            Integer key = entry.getKey();
            Integer value = entry.getValue();

            List<Integer> pair = new ArrayList<Integer>(); //make a pair
            pair.add(key);
            pair.add(value);

            //System.out.println(pair);

            Node newNode = new Node(pair);

            System.out.println(newNode.data);

            if(sortedList == null) {
                //System.out.println(newNode.data);
                newNode.next = sortedList;
                sortedList = newNode; //insert at head if linked list is empty
            } else {
                Node current = sortedList; //point current to head
                //move current pointer until we find a spot where current's frequency is less than newNode's frequency
                while(current.next != null && current.next.data.get(1) < newNode.data.get(1)) {
                    current = current.next;
                }
                    newNode.next = current.next;
                    current.next = newNode;
            }

        }

        int count = 0;

        //loop until k and return first k keys
        while(sortedList != null && count < k) {
            //System.out.println("key:"+sortedList.data.get(0) + " value:"+ sortedList.data.get(1));
            res.add(sortedList.data.get(0));
            sortedList = sortedList.next;
            count++;
        }


        return res;
    }

    class Node {     
        List<Integer> data = new ArrayList<Integer>();
        Node next;

        Node(List<Integer> pair) {
            data = pair;
        }
    }
}

Однако по какой-то причине мой LinkedListзаполняется как head -> [1,3] -> [3,1] -> [2,2] -> null вместо надлежащего отсортированного способа.Я пытался отладить его, но не смог выяснить, какую часть я испортил.Я также написал это на бумаге, и это, кажется, работает, так что я уверен, что что-то напутал в моем коде.

Что я здесь не так делаю?

1 Ответ

0 голосов
/ 27 сентября 2018

Проблема в куске кода, где вы пытаетесь вставить в связанный список в отсортированном порядке.Первое, что вы начинаете сравнение с current.next.data, вы должны начинать сравнение с самого первого узла.Во-вторых, вы не обрабатывали случай, когда элемент должен быть вставлен в последний узел, а также в самый первый узел.и у вас есть условие <, что означает, что оно будет вставлено в порядке убывания.

Внутри кода итерации карты замените условие if else на приведенный ниже код. Оно отлично работает 

 if(sortedList == null) {
                    //System.out.println(newNode.data);
                    newNode.next = sortedList;
                    sortedList = newNode; //insert at head if linked list is empty
                } else {
                    Node current = sortedList; //point current to head
                    Node prev=null;
                    //move current pointer until we find a spot where current's frequency is less than newNode's frequency
                    while(current != null && current.data.get(1) > newNode.data.get(1)) {
                        prev=current;
                        current = current.next;
                    }
                    if(current==null) {
                        prev.next=newNode;
                    }else if(current==sortedList) {
                        newNode.next=current;
                        sortedList=newNode;
                    }
                    else {
                        newNode.next = current.next;
                        current.next = newNode;
                    }


                }

Здесь, если current==null означает, что данные должны быть вставлены в последний и последний узел, и в это время последний узел будет ссылаться на prev , поэтому prev.next=newNode; назначит newNodeдлиться.если current==sortedList означает, что данные должны быть вставлены в первый узел.в противном случае данные должны быть вставлены посередине.

...