java - 尝试使用 LinkedList 解决前 K 个频繁出现的元素

Question

我正在尝试解决 LeetCode #347. Top K Frequent Elements .我知道有几种方法可以解决这个问题，但我正尝试通过以下方式来解决。

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) 打印这个LinkedList的前k个值元素，即。 [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 而不是正确的排序方式。我试过调试它，但一直无法弄清楚我搞砸了哪一部分。我还把它写在纸上，它似乎有效，所以我确定我的代码搞砸了。

我在这里做错了什么？

Answer 1

问题出在您尝试将链接列表插入排序顺序的代码段中。第一件事是你从 current.next.data 开始比较您应该从第一个节点开始比较。其次，您没有处理必须在最后一个节点和第一个节点插入元素的情况。你有条件 <这意味着它将按降序插入。

里面的 map 迭代代码replace 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意味着必须在最后一个节点插入数据，那时 last node 将被 prev 引用所以 prev.next=newNode;会将 newNode 分配给 last。如果current==sortedList意味着必须在第一个节点插入数据。否则需要在中间插入数据。