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 for
AddNum, findMedian
for50000
Time 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