Find Kth largest element in an integer array

[GingerBear]

给一个整数数组和一个整数K，返回在数组中第K大的元素。分析一下时间与空间复杂度。如果能养成写test case的习惯就更好了。

如果不用排序的方法呢？

经典题，我在面试亚马逊的时候碰到过。想想如果不允许排序的话该怎么做？如果已经知道怎么做了，尝试在记事本里着快速写出。

[dianadujing]

用assert?

[GingerBear]

@dianadujing 没有用过Java的assert，最近看JavaScript和Ruby on Rails的书才意识到test的必要性，我的做法是自定义一个简单的simpleAssert()，就是在true和false的打印不同的值，带上msg。

static void simpleAssert(Boolean ifSuccess, String msg){
    if (ifSuccess) {
        System.out.println("SUCCESS:\t" + msg);
    }else{
        System.out.println("FAILS:\t" + msg);
    }
}

使用起来也很简单：

simpleAssert(fib2(1) == 1, "fib2: 1");

我想，如果在面试的时候，coding完还能带上test case的话一定能加分不少。

对了，如果你研究出来Java里一般是如何测试的，能不能也分享一下？

[dianadujing]

@GingerBear 有人在stackoverflow上问过我问的问题，得到的答案特别简单，但我觉得确实最靠谱 http://en.wikipedia.org/wiki/Unit_testing

[dianadujing]

不允许sort, 就一直一半一半地找，貌似叫什么median, 稍后上代码

[dianadujing]

Using quick select algorithm:

public class KthLargetst {
    public static int findKthLargest(int[] input, int k){
        return quickselect(input, 0, input.length-1, k-1);
    }

    private static int quickselect(int[] input, int first, int last, int k) {
        if(first<=last){
            int pivot = partition(input, first, last);
            if(pivot == k) {
                return input[k];
            }
            if(pivot>k){
                return quickselect(input, first, pivot-1, k);
            }
            return quickselect(input, pivot+1, last, k);
        }
        return 0;
    }

    private static int partition(int[] input, int first, int last) {
        int pivot = (first+last)/2;
        swap(input, last, pivot);//put the pivot at the end
        for(int i=first;i<last;i++){
            if(input[i]>input[last]){//compare current one with pivot
                swap(input, i, first);
                first++;
            }
        }
        swap(input, first, last);//put pivot back to the right place
        return first;
    }

    private static void swap(int[] input, int a, int b) {
        int temp = input[a];
        input[a]=input[b];
        input[b]=temp;
    }
}

[GingerBear]

@dianadujing 非常NB！请分析一下复杂度？

[allen6432]

code很棒！！！但是有个小错误：这个代码找出来的是第k小的元素

[allen6432]

不好意思是我搞错了。没有问题！！！

[allen6432]

这个code真心很牛掰啊！自己代码能力确实太差！我这里算了一下它的时间复杂度，确实竟然是O(n)!!!!果然迅猛！！！ 我把过程贴下来，有错误请指出！！！

2014-01-20 00 34 10

[allen6432]

不好意思。。。刚图没有贴上

[allen6432]

我大致算了一下，如果我们不取中间点为pivot,取任意random,其实这个的平均时间复杂度应该没有影响。不过我暂时不确定，明天算算再发上来。ps： 这个code真心简洁

[GingerBear]

开了一个新贴总结Heap这个数据结构，包括了用Heap来解决这道问题的方法 #10

[allen6432]

@GingerBear @dianadujing 大神们，来一期关于tries的类容？有没有想法？？？

[GingerBear]

用Heap求第K大元素的Java代码，这个方法确实没有quicksort的方法好，不过借此机会来复习一下Heap也不错。算法的原理不复杂，但实现起来却比较麻烦，主要需要考虑“数组越界”的情况和使用while循环来“iteratively找到元素合适位置”。

// define error message, not a good way, throw error is better
public static int ERROR_NUM = Integer.MIN_VALUE;

// turn array into heap
static void heapify(int[] arr, int n) {
    int root = n/2 - 1; // the first tree at the bottom
    int curr = 0, bigger_child = 0;

    // start from the first tree in the bottom right to left top trees
    while (root >= 0) {
        curr = root; // store root to a tmp variable curr for recursively compare to child
        while (curr < n / 2) {
            if (curr*2 + 2 > n - 1) { // check if have just one child, prevent array out bround error
                if (arr[curr] < arr[curr*2 + 1]) {
                    bigger_child = arr[curr*2 + 1];
                } else {
                    break; // find the right place
                }
            } else {
                if (arr[curr] < Math.max(arr[curr*2 + 1], arr[curr*2 + 2])) {
                    bigger_child = arr[curr*2 + 1] > arr[curr*2 + 2] ? curr*2 + 1 : curr*2 + 2;
                } else {
                    break;
                }
            }
            swap(arr, curr, bigger_child);
            curr = bigger_child;
        }
        root--;
    }
}

static int heapDelete(int[] heap, int n) {
    int ret = heap[0];
    heap[0] = heap[n-1];
    int root = 0, bigger_child = 0;

    // restore: if parent is less than the bigger child, swap
    while (root < n / 2) {
            if (root*2 + 2 > n - 1) {
                if (heap[root] < heap[root*2 + 1]) {
                    bigger_child = heap[root*2 + 1];
                } else {
                    break;
                }
            } else {
                if (heap[root] < Math.max(heap[root*2 + 1], heap[root*2 + 2])) {
                    bigger_child = heap[root*2 + 1] > heap[root*2 + 2] ? root*2 + 1 : root*2 + 2;
                } else {
                    break;
                }
            }
            swap(heap, root, bigger_child);
            root = bigger_child;
    }
    return ret;
}

static void swap(int[] arr, int i1, int i2) {
    int tmp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = tmp;
}

static int findKLarge(int[] arr, int k) {
    if (arr.length == 0 || k > arr.length)
        return ERROR_NUM; 
    int ret = 0;
    int n = arr.length;

    heapify(arr, n);

    for (int i = 0; i < k; i++) {
        ret = heapDelete(arr, n--);
    }

    return ret;
}

public static void main (String [] args) {
    int[] arr1 = {32, 322, 123, 24, 1, 1223, 432, 2};
    int[] arr2 = {};
    int[] arr3 = {12, 432, 2, 234, 23, 23};

    simpleAssert( findKLarge(arr1, 4) == 123, "regular");
    simpleAssert( findKLarge(arr2, 4) == ERROR_NUM, "bad call with empty array");
    simpleAssert( findKLarge(arr3, 12) == ERROR_NUM, "bad call with index overflow");
}

static void simpleAssert(boolean ifTrue, String msg) {
    String m = ifTrue ? "SUCCESS\t" : "FAILED\t";
    System.out.println(m+msg);
}

[GingerBear]

@allen6432 tries? 没有听说过诶，好像很高级。那这光荣的任务就交给你啦！

[dianadujing]

@GingerBear cc150 p84. 就是每一个树杈上的所有node从上到下连起来是一个词

[allen6432]

@dianadujing cc150是哪本书？

[dianadujing]

@allen6432 Cracking the Coding interview