题解 | #寻找第K大#

我没有用题目给出的快速排序的思路来做这道题，我也很菜，所以不知道这方法是复杂了还是怎么的。

思路：创建一个Map来存放从最大值开始遍历来的值value和次数count，如果count < K，就继续去遍历比value值小的一个数，此时K = K-count;如果count > K，则跳出循环，返回Map保存的value。
相当于在这个题中，数组长度n没什么用。

遍历函数getMap()详解：
临时变量temp保存较大值，count保存出现的次数;
当map不为空时，说明上一次遍历出的值的次数count < K；所以需要继续遍历，但此次遍历的最大的值要小于上次遍历的值map.get("value")；
所以在此函数的循环中，只需要找出比 上次遍历值 小的最大值和次数；在遍历过程中，一旦出现比temp大数，将该值赋给temp；同时count重新记为1；
最后找出此次遍历出来的最大值temp和其次数count，清空上次遍历的map，再将此次遍历的值放出map，返回map；

    public int findKth(int[] a,int n, int K) {
        // write code here
        Map<String, Integer> map = new HashMap<>();
        map = getMap(map,a);
        int value;
        int count;
        while(true){
            value = map.get("value");
            count = map.get("count");
            if(count >= K){
                break;
            }else{
                K = K-count;
                map = getMap(map,a);
            }
        }
        return value;
    }


    private Map getMap(Map map,int[] arr){
        int temp = -1;
        int count = -1;

        int top = 0;
        boolean flag = false;
        if(!map.isEmpty()){
            flag = true;
            top = (Integer) map.get("value");
        }

        for(int i = 0;i < arr.length;i++){
            if(flag){
                if(arr[i] < top){
                    if(temp == arr[i]){
                        count++;
                    }
                    if(temp == -1 && count == -1) {
                        temp = arr[i];
                        count = 1;
                    }

                    if(temp < arr[i]){
                        temp = arr[i];
                        count = 1;
                    }
                }
            }else{
                if(temp == arr[i]){
                    count++;
                }

                if(temp == -1 && count == -1) {
                    temp = arr[i];
                    count = 1;
                }

                if(temp < arr[i]){
                    temp = arr[i];
                    count = 1;
                }
            }
        }
        map.clear();
        map.put("value",temp);
        map.put("count",count);
        return map;
    }