美文网首页
寻找最小的 k 个数

寻找最小的 k 个数

作者: MinoyJet | 来源:发表于2017-07-29 19:35 被阅读0次

    寻找最小的 k 个数

    题目描述:

    输入 n 个整数,输出其中最小的 k 个。

    分析和解法:

    解法一:排序输出

    要求一个序列中最小的 k 个数,按照惯有的思维方式,则是先对这个序列从小到大排序,然后输出前面的最小的 k 个数。
    当然,选取什么排序算法都是可以的。为了效率,我们可以使用快排来进行排序,然后再遍历序列中前k个元素输出即可。
    源代码如下:

    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    
    int Compare(const void *elem1, const void *elem2)
    {
        return *((int *)(elem1)) - *((int *)(elem2));
    }
    
    int main()
    {
        int a[100];
        int i = 0;
        char ch;
        while((ch = cin.get()) != '\n')  //此处也可以用 cin.peek() ,只预读,不取出 
        {
            cin.unget();
            cin >> a[i++];
        }
        int k;
        cin >> k;
        qsort(a, i, sizeof(int), Compare);
        if (i >= k)
        {
            for (int j = 0; j < k; j++)
                cout << a[j] << " ";
            cout << endl;
        }
        else 
            cout << "error: i < k";
        return 0;
    }
    

    分析:时间复杂度为 O(n * log n),但是这个方法修改了原有数据顺序,如果要求不许改变原始数据,则可以复制到另一数组去做。虽然可以解决问题,但是却做了许多无用功。

    解法二:部分排序

    题目没有要求最小的 k 个数有序,也没要求最后 n - k 个数有序。既然如此,就没有必要对所有元素进行排序。这时,就可以用选择排序或交换排序,即:

    • 1、遍历 n 个数,把最先遍历到的 k 个数存入到大小为 k 的数组中,假设它们即是最小的 k 个数;
    • 2、对这 k 个数,利用选择或交换排序找到这 k 个元素中的最大值kmax(找最大值需要遍历这 k 个数,时间复杂度为 O(k));
    • 3、继续遍历剩余 n - k 个数。假设每一次遍历到的新的元素的值为 x ,把 x 与 kmax 比较:如果 x < kmax ,用 x 替换 kmax,并回到第二步重新找出 k 个元素的数组中最大元素 kmax;如果 x >= kmax ,则继续遍历不更新数组。

    源代码如下:

    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    
    void Swap(int &a, int &b)
    {
        int temp = a;
        a = b;
        b = temp; 
    }
    
    int FindKMAX(int a[], int k)
    {
        for(int i = 1; i < k; i++)
            if (a[0] < a[i])  Swap(a[0], a[i]);
        return a[0];  // a[0] 是 KMAX 
    }
    
    int main()
    {
        int a[100];
        int i = 0;
        char ch;
        while((ch = cin.get()) != '\n')  //此处也可以用 cin.peek() ,只预读,不取出 
        {
            cin.unget();
            cin >> a[i++];
        }
        int k;
        cin >> k;
        int KMAX = FindKMAX(a, k);
        for (int j = k; j < i; j++)
        {
            if (KMAX > a[j])
                Swap(a[0], a[j]);
            else 
                continue;
            KMAX = FindKMAX(a, k);
        }
        for (int j = 0; j < k; j++)
            cout << a[j] << " ";
        cout << endl;
        return 0;
    }
    

    分析:每次遍历,更新或不更新数组的所用的时间为 O(k) 或 O(0) 。故整趟下来,时间复杂度为 n * O(k)=O(n * k) 。这种方法是无序输出的,只关心最小的 k 个数,具体谁大谁小并不关心。

    解法三:维护最大堆

    更好的办法是维护容量为k的最大堆,原理跟解法二的方法相似:

    • 1、用容量为 k 的最大堆存储最先遍历到的 k 个数,同样假设它们即是最小的 k 个数;
    • 2、堆中元素是有序的,令 k1 < k2 < ... < kmax (kmax 设为最大堆中的最大元素)
    • 3、遍历剩余 n - k 个数。假设每一次遍历到的新的元素的值为 x,把 x 与堆顶元素 kmax 比较:如果 x < kmax ,用 x 替换 kmax,然后更新堆(用时 log k);否则不更新堆。

    源代码如下:

    #include <iostream>
    #include <cstdlib>
    
    #define LEFT(i) (2 * (i) + 1)
    #define RIGHT(i) (2 * ((i) + 1))
    
    using namespace std;
    
    void Swap(int &a, int &b)
    {
        int temp = a;
        a = b;
        b = temp; 
    }
    
    //此函数把一颗二叉树中以 node 为根的子树变成最大堆。
    //注意: 使用的前提条件是 node 节点的左右子树(如果存在的话)都是最大堆。
    void MaxHeapify(int heap[], int heap_size, int node) 
    {
        int l_child = LEFT(node);
        int r_child = RIGHT(node);
        int max_value = node;
        if (l_child < heap_size && heap[l_child] > heap[max_value])
            max_value = l_child;
        if (r_child < heap_size && heap[r_child] > heap[max_value])
            max_value = r_child;
        if (max_value != node)
        {
            Swap(heap[node], heap[max_value]);
            // 之后还要保证被交换的子节点构成的子树仍然是最大堆
            // 如果不是这个节点会继续"下沉",直到合适的位置
            MaxHeapify(heap, heap_size, max_value);
        }
    }
    
    void BuildMaxHeap(int heap[], int heap_size)
    {
        if (heap_size < 2)
            return;
            
        int first_leaf = heap_size >> 1;   //first_leaf = heap_size / 2;
        int i;
        //从最后一个非叶子节点开始自底向上构建
        for (i = first_leaf - 1; i >= 0; i--)
            MaxHeapify(heap, heap_size, i); 
    }
    
    int main()
    {
        int a[100];
        int i = 0;
        char ch;
        while((ch = cin.get()) != '\n')  //此处也可以用 cin.peek() ,只预读,不取出 
        {
            cin.unget();
            cin >> a[i++];
        }
        int k;
        cin >> k;
        BuildMaxHeap(a, k);
        for (int j = k; j < i; j++)
        {
            int KMAX = a[0];
            if (KMAX > a[j])
                Swap(a[0], a[j]);
            else 
                continue;
            MaxHeapify(a, k, 0);
        }
        for (int j = 0; j < k; j++)
            cout << a[j] << " ";
        cout << endl;
        return 0;
    }
    

    分析:这样下来,总的时间复杂度: O(k +(n - k)* log k)= O(n * log k) 。此方法得益于堆中进行查找和更新的时间复杂度均为: O(log k)(若使用解法二:在数组中找出最大元素,时间复杂度: O(k)) 。

    特别注意:

    • cin.peek() 只预读,不提取流数据,并且不会跳过空格和回车
    • 还有一些更高效率的算法,并且也有一些可以提高上面算法的一些小的改进,有兴趣的可以看看下面的参考资料

    参考资料:《编程之法》The Art of Programming By July
    找最小的K个数

    相关文章

      网友评论

          本文标题:寻找最小的 k 个数

          本文链接:https://www.haomeiwen.com/subject/hvtclxtx.html