yulu

算法-寻找第K小的数

发表于

题目：给定一个数组A，找出数组中前K个最小的数

分析：最直观的想法应该是排序，排完序之后输出前K个数就ok了。排序可以用平均复杂度为O(n * logn)的快速排序。但题目并没有要求输出的前K个最小数有序，既然如此，就没有必要为所有元素排序。我们可以采用其他方法。 即：

  1. 取A中前K个数，假设这就是数组A中最小的K个数。
  2. 对选出的K个数取最大值max_tmp。
  3. 遍历数组A中剩余的数，如果A[i] < max_tmp 则交换max_tmp,A[i]的位置，然后重复步骤2；如果A[i] > max_tmp,则不做任何处理。
  4. 输出数组A中前K个元素即为最小的K个数。
    每次遍历更新或不更新数组的时间复杂度为O(K)或者O(0),所以最终时间复杂度为n * O(K);
    代码实现如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    <?php
    function find($arr,$k)
    {
    	$len = count($arr);
    	if($len <= $k){
    		return $arr;
    	}
    	$i = findMinItem($arr,$k);
    	for($index = $k; $index < $len; $index++){
    		if($arr[$index] < $arr[$i]){
    			$tmp = $arr[$index];
    			$arr[$index] = $arr[$i];
    			$arr[$i] = $tmp;
    			$i = findMinItem($arr,$k);
    		}
    	}
    	return $arr;
    }
    function findMinItem($arr,$end)
    {
    	$index = 0;
    	$minTmp = $arr[0];
    	for($i = 0; $i < $end; $i++){
    		if($arr[$i] > $minTmp){
    			$index = $i;
    		}
    	}
    	return $index;
    }
    $arr = [9,8,7,6,5,4,3,2,1];
    $ret = find($arr,2);
    print_r($ret);

除此之外还有其他方法，类似与使用堆排序来构建临时数组，由于堆中的数据是已经排好序的，每次取数组A中的元素与堆顶元素做比较，如果小于堆顶元素则替换堆顶元素，并重新构建堆；否则不更新堆。