剑指offer

 答案自建堆：用一个大根堆维护数组的前k个小值，然后从k+1开始遍历，如果遍历到的数比堆顶的数小，就d出堆顶的数，插入当前数，最后将大根堆里的数存入数组返回。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        //堆排
        int[] res=new int[k];
        if(k==0){
            return res;
        }
        //创建一个优先队列-难点
        PriorityQueue queue = new PriorityQueue(
            //匿名内部类
            new Comparator() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for(int i=0;i 
快排：
 
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        //快排
       quick(arr,0,arr.length-1);
       int[] r=new int[k];
       for(int i=0;ipivot){
                r--;
            }

            //直到左指针大于等于右指针才结束
            if(l>=r){
                break;
            }
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
            //说明pivot已经被换到左边了，所以右指针要左移
            if(arr[l]==pivot){
                r--;
            }
            //说明此时，pivot已经被换到右边了，所以左指针要继续右移
            if(arr[r]==pivot){
                l++;
            }

        }
        //如果左边等于右边，可能会锁死循环
        if (r==l){
            r--;
            l++;
        }
        //
        if(leftl){
            quick(arr,l,right);
        }
    }
}
 
答案给的快排就是比尚硅谷这个快：9ms和2ms的区别
 
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        randomizedSelected(arr, 0, arr.length - 1, k);
        int[] vec = new int[k];
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }

    private void randomizedSelected(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomizedPartition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomizedSelected(arr, l, pos - 1, k);
        } else {
            randomizedSelected(arr, pos + 1, r, k - num);
        }
    }

    // 基于随机的划分
    private int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
 
答案二叉搜索树：
 
 
 
 
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        TreeMap map = new TreeMap<>();
        int cnt = 0;
        for (int num: arr) {
            if (cnt < k) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                cnt++;
                continue;
            } 
            Map.Entry entry = map.lastEntry();
            if (entry.getKey() > num) {
                map.put(num, map.getOrDefault(num, 0) + 1);
                if (entry.getValue() == 1) {
                    map.pollLastEntry();
                } else {
                    map.put(entry.getKey(), entry.getValue() - 1);
                }
            }
            
        }
        int[] res = new int[k];
        int idx = 0;
        for (Map.Entry entry: map.entrySet()) {
            int freq = entry.getValue();
            while (freq-- > 0) {
                res[idx++] = entry.getKey();
            }
        }
        return res;
    }
}
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/577591.html