美文网首页
寻找最小的 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 个数

    寻找最小的 k 个数 题目描述: 输入 n 个整数,输出其中最小的 k 个。 分析和解法: 解法一:排序输出 要求...

  • 寻找最小的k个数

    http://taop.marchtea.com/02.01.html 有平均O(n)的快速选择算法哦!比最大堆的...

  • Algorithm

    bit manipulation 动态规划 0-1背包问题 寻找最小的k个数

  • 算法-数组(三)

    最小的k个数 求子数组的最大和 把数组排成最小的数字 1.最小的k个数 问题描述:输入n个数字,找到数组中最小的k...

  • 06-20:刷题综合三:快排

    快排: 1、快速排序 2、快速排序寻找第K个大 3、最小的K个数 1、手写快排算法 class Solution:...

  • 最小的k个数

    问题描述:输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是...

  • 最小的k个数

    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3...

  • 最小的K个数

    题目描述输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1...

  • 最小的k个数

    参考: [1] https://www.nowcoder.com/questionTerminal/6a296eb...

  • 最小的K个数

    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。

网友评论

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

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