求一个数组中最小的K个数

浏览数：16 / 时间：2015年06月08日

方法1：先对数组进行排序，然后遍历前K个数，此时时间复杂度为O(nlgn);

方法2：维护一个容量为K的最大堆（《算法导论》第6章），然后从第K+1个元素开始遍历，和堆中的最大元素比较，如果大于最大元素则忽略，如果小于最大元素则将次元素送入堆中，并将堆的最大元素删除，调整堆的结构;

方法3：使用复杂度为O(n)的快速选择算法.....................

/**
 * Created by elvalad on 2014/12/8.
 * 输入N个整数，输出最小的K个
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class MinKArray {
    /* 用二叉树表示一个堆 */
    private class Heap {
        private Node root;
        private class Node {
            int key;
            Node left;
            Node right;
            Node(int key) {
                this.key = key;
            }
        }

        /* 建立最大堆，将元素插入到堆的合适位置 */
        public void put(int key) {
            root = put(root, key);
        }

        private Node put(Node x, int key) {
            if (x == null)
                return new Node(key);
            int cmp = key - x.key;
            if (cmp > 0) {
                int tmp = x.key;
                x.key = key;
                key = tmp;
                x.right = put(x.right, key);
            } else if (cmp < 0) {
                x.left = put(x.left, key);
            }
            return x;
        }

        public void deleteMax() {
            root = deleteMax(root);
        }

        private Node deleteMax(Node x) {
            if (x == null)
                return null;
            if ((x.left == null) && (x.right != null)) {
                int tmp = x.key;
                x.right.key = x.key;
                x.key = tmp;
                x.right = deleteMax(x.right);
            } else if ((x.right == null) && (x.left != null)) {
                int tmp = x.key;
                x.left.key = x.key;
                x.key = tmp;
                x.left = deleteMax(x.left);
            } else if ((x.left == null) && (x.right == null)) {
                x = null;
            } else {
                int cmp = x.left.key - x.right.key;
                if (cmp >= 0) {
                    int tmp = x.key;
                    x.key = x.left.key;
                    x.left.key = tmp;
                    x.left = deleteMax(x.left);
                } else {
                    int tmp = x.key;
                    x.key = x.right.key;
                    x.right.key = tmp;
                    x.right = deleteMax(x.right);
                }
            }
            return x;
        }

        public void printHeap(Node x) {
            if (x == null)
                return;
            System.out.println(x.key);
            printHeap(x.left);
            printHeap(x.right);
        }
    }

    /* 使用一般的排序算法，然后顺序输出前K个元素 */
    public int[] minKArray1(int[] a, int k) {
        Arrays.sort(a);
        for (int i = 0; i < k; i++) {
            System.out.println(a[i]);
        }
        return Arrays.copyOfRange(a, 0, k);
    }

    /* O(n)算法实现快速选择算法 */
    public int[] minKArray2(int[] a, int k) {
        return a;
    }

    /* 维护一个容量为K的最大堆，《算法导论》第6章堆排序 */
    public int[] minKArray3(int[] a, int k) {
        Heap h = new Heap();
        for (int i = 0; i < k; i++) {
            h.put(a[i]);
        }
        for (int i = k; i < a.length; i++) {
            if (a[i] >= h.root.key) {
                continue;
            } else {
                h.put(a[i]);
                h.deleteMax();
            }
        }
        h.printHeap(h.root);
        return a;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        ArrayList<Integer> array = new ArrayList<Integer>();
        while (scan.hasNext()) {
            array.add(scan.nextInt());
        }
        int[] a = new int[array.size()];
        for (int i = 0; i < a.length; i++) {
            a[i] = array.get(i);
        }
        MinKArray mka = new MinKArray();
        mka.minKArray1(a, 8);
        System.out.println("---------------");
        mka.minKArray3(a, 8);
    }
}