544. 545.Top k Largest Numbers I II

Leave a comment

August 24, 2016 by oneOokay

544. Top k largest numbers I

Heap & Priority Queue 和quicksort的方法。

Heap & PriorityQueue:重点是:PriorityQueue/heap只能保证他的最顶点是整个结构的最小或最大值。除此以外的其他元素都是无序的,由于lintcode对输出有要求按从大到小排序,所以从heap里面取出来之后要重新排一下序。在求largest的问题的时候,需要用到minheap,最小堆。

public int[] topk(int[] nums, int k) {
Queue<Integer> minheap = new PriorityQueue<Integer>();
for (int i = 0; i < nums.length; i ++) {
if(minheap.size() < k) //限定minheap的大小来存top k个数
{
minheap.offer(nums[i]);
continue;
}

if(nums[i] > minheap.peek()){ //当新的值大于minheap的顶端值时(minheap的顶端值为整个heap的最小值)
minheap.poll(); //把minheap的顶端拿掉,加入新的值。然后minheap会自动排序,把新的整个heap的最小值放到顶端,其他依旧无序
minheap.offer(nums[i]);
}
}

Iterator it = minheap.iterator();
List<Integer> tmp = new ArrayList<Integer>();
while(it.hasNext()){
tmp.add((Integer)it.next());
}
Collections.sort(tmp, Collections.reverseOrder()); //利用list来进行排序
int[] result = new int[k];
for (int i = 0; i < k; i ++) {
result[i] = tmp.get(i); //转换到array中输出
}
return result;
}

quicksort:有两种不同quicksort的方法:

  • 普通方法,quick sort整个 array,之后再取前k个数。
    • 复习一下quick sort. time complexity: O(nlogn) best/average. O(n^2) worst。
    • quick sort:从小到大quick sort和从大到小quick sort
  • 九章的优化方法:quicksort 部分array,使得array前k个数为整体最大的k个数(注意此时前k个数虽然为top k largest,但是并不是有序的),在将这前k个数进行排序之后输出。然后它还是通过一个random数来找pivot,并不太清楚为什么要这样做。。。

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

应该把这个里面提到的方法都实现一遍。

class Solution {
public int[] topk(int[] nums, int k) {
if (nums == null || nums.length < k) {
return null; }

quickSort(nums, 0, nums.length – 1, k); //传入k,quick sort之后的前k个数是无序的,接下来用一个List的Collections.sort来进行排序
List<Integer> tmp = new ArrayList<Integer>();
for (int i = 0; i < k && i < nums.length; i ++) {
tmp.add(nums[i]);}
Collections.sort(tmp, Collections.reverseOrder()); //reverseOrder()从大到小排,若默认排序的话,就不需要Collections.reverseOrder()了
int[] result = new int[k];
for (int i = 0; i < k ; i ++ )
{result[i] = tmp.get(i);}
return result;}

//这是一个由大到小的quick sort
private void quickSort(int[] A, int start, int end, int k) {
if (start >= k || end < k) {return;} //start >= k时,start之前的数已经是整个list中前k个大的数了;end < k时,end之后的数已经是整个数组中小于end之前的数,所以此时end之前的数为整个数组中前k个最大的数。
if (start >= end) {
return;
}

int pivot = A[(start + end) / 2];
int left = start;
int right = end;
while (left <= right) {
while (left <= right && A[left] > pivot) { //这里决定了是从小到大排还是从大到小排
left ++;
}
while (left <= right && A[right] < pivot) {//这里决定了是从小到大排还是从大到小排
right –;
}

if(left <= right) {
int tmp = A[left];
A[left] = A[right];
A[right] = tmp;
left ++;
right –;}}
quickSort(A, start, right, k);
quickSort(A, left, end, k);
}
};

545 : Top k Largest Number II

同I没有什么太大的区别,直接用minheap

public class Solution {

private int maxSize;
private Queue<Integer> minheap;
public Solution(int k) {
// initialize your data structure here.
minheap = new PriorityQueue<>();
maxSize = k;
}

public void add(int num) {
// Write your code here
if(minheap.size() < maxSize) {
minheap.offer(num);
return;
}

if (num > minheap.peek())
{
minheap.poll();
minheap.offer(num);
}
}

public List<Integer> topk() {
// Write your code here
Iterator it = minheap.iterator();
List<Integer> result = new ArrayList<Integer>();
while(it.hasNext()){
result.add((Integer)it.next());
}
Collections.sort(result, Collections.reverseOrder());
return result;
}
};

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: