package easy;

import java.util.HashMap;
import java.util.Map;

public class TopKFrequent {
    public static void main(String[] args) {
        new TopKFrequent().topKFrequent(new int[]{1},1);
    }
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> numCount=new HashMap<>(nums.length/2);
        for (int num : nums) {
            if (numCount.containsKey(num)){
                numCount.replace(num,numCount.get(num)+1);
                continue;
            }
            numCount.put(num,1);
        }
        int[] result=new int[k];
        Node head=new Node();
        Node index=head;
        for (int i = 1; i < k; i++) {
            index.next=new Node();
            index=index.next;
        }
        Node nodbuf;
        for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {
            index=head;
            nodbuf=new Node(entry.getKey(),entry.getValue());
            if (entry.getValue()>index.count){
                nodbuf.next=index;
                head=nodbuf;
                removeEnd(head);
                continue;
            }
            while (index.next!=null){
                if (entry.getValue()>index.next.count){
                    nodbuf.next=index.next;
                    index.next=nodbuf;
                    removeEnd(head);
                    break;
                }
                index=index.next;
            }
        }
        for (int i = 0; i < k; i++) {
            result[i]=head.value;
            head=head.next;
        }
        return result;
    }

    public void removeEnd(Node node){
        if (node.next==null){
            return;
        }
        while (node.next.next!=null){
            node=node.next;
        }
        node.next=null;
    }

    class Node{
        Node(int value,int count){
            this.value=value;
            this.count=count;
        }
        Node(){
            value=-1;
            count=-1;
        }
        Node next;
        int count;
        int value;
    }
}

?