MyException - 我的异常网
当前位置:我的异常网» 行业应用 » 找到数组中第k小的元素

找到数组中第k小的元素

www.MyException.Cn  网友分享于:2013-02-20  浏览:5次
找出数组中第k小的元素

给定一无序整型数组a,在不排序的情况下,查找第k小的元素

类似快排。

如果k非常小比如小于3,觉得应该用几个临时变量然后遍历一遍解决。

 

public class MinKth {
    public static int calculate(int[] array, int k) {
        return calculate(array, k, 0, array.length - 1);
    }

    public static int calculate(int[] array, int k, int low, int high) {
        int target = array[low];
        int i = low;
        int j = high;

        while (i < j) {
            while (i <= high && array[i] <= target) {
                i++;
            }
            while (j >= low && array[j] > target) {
                j--;
            }

            if (i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        int tmp = array[j];
        array[j] = array[low];
        array[low] = tmp;

        int gap = i - low + 1;
        if (gap > k)
            return calculate(array, k, low, i - 1);
        if (gap < k)
            return calculate(array, k - gap, i + 1, high);
        else
            return array[i];
    }
}

 

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有