The smallest number of k

Enter the integer array arr to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4.

Input: arr = [3,2,1], k = 2 output: [1,2] or [2,1]Copy the code
Input: arr = [0,1,2,1], k = 1Copy the code

Limitations:

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

Leetcode-cn.com/problems/zu…

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0; i<arr.length; i++){
            queue.offer(arr[i]);
        }
        int[] result = new int[k];
        for(int i=0; i<k; i++){
            result[i] = queue.poll();
        }
        returnresult; }}Copy the code

The median in the data stream

How do I get a median in a data stream? If an odd number of values are read from the data stream, the median is the number in the middle of all values sorted. If an even number of values are read from the data stream, the median is the average of the middle two numbers sorted by all the values.

For example,

The median of [2,3,4] is 3

The median of [2,3] is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • Void addNum(int num) – Adds an integer from the data stream to the data structure.
  • Double findMedian() – Returns the current median for all elements.
Input: [" MedianFinder ", "addNum", addNum ""," findMedian ", "addNum", "findMedian"] [[], [1], [2], [], [3], []] output: [null, null, null, 1.50000, null, 2.00000]Copy the code
Input: [" MedianFinder ", "addNum", "findMedian", "addNum", "findMedian"] [[], [2], [], [3], []] output: [null, null, 2.00000, null, 2.50000]Copy the code

Limitations:

  • Most meeting forAddNum, findMedianfor50000Time to call.
class MedianFinder {

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    /** initialize your data structure here. */
    public MedianFinder(a) {
        left = new PriorityQueue<>(Comparator.reverseOrder());
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        left.add(num);
        right.add(left.poll());
        if(left.size() +1< right.size()){ left.add(right.poll()); }}public double findMedian(a) {
        if(right.size() > left.size()){
            return right.peek();
        }
        return (double)(left.peek()+ right.peek()) /2; }}/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); * /
Copy the code