不使用Sort或LinqOrderBy方法的无序数组中的前K个数字

本文关键字：数组 数字 无序 Sort LinqOrderBy 方法 | 更新日期: 2023-09-27 18:20:52

我只是在谷歌上搜索.Net中的内置函数，从未排序的数组中获取前K个数字/元素，而不使用linq order by或sort方法。

另一种方法是，我可以通过实现选择算法来编写自己的TopK方法。

但我的主要意图是"是否有使用快速选择或堆之类的选择算法的内置功能。"

如果没有内置的TopK方法，我想知道如何在不使用Sort和OrderBy方法的情况下使用Linq或.Net

避免使用Sort和OrderBy的原因是"它们在内部遵循排序算法，而不是选择算法"。如果我错了，请纠正我。

不使用Sort或LinqOrderBy方法的无序数组中的前K个数字

这个怎么样：

void Main()
{
    var kth = 4;
    var arr = new int [] {5, 1, 3, 4, 2, 1};
    var val = getItem(arr, kth);
}   
int getItem(int[] items, int kth)
{
    if (kth == 0 || kth > items.Length)
    {
        throw new  IndexOutOfRangeException();
    }
    else if (items.Length == 1 && kth == 1)
    {
        // only 1 item so return it
        return items[0];
    }
    else if (items.Length == 2)
    {
        if (kth ==1)
        {
            // two items, 1st required so return smallest   
            return (items[0] <= items[1] ? items[0] : items[1]);
        }
        else
        {
            // two items, 2nd required so return smallest   
            return (items[0] <= items[1] ? items[1] : items[0]);
        }
    }
    var middleItem = (int)((items.Length)/2);
    var pivot = items[middleItem];
    var leftarr = items.Where(s => s < pivot).ToArray();
    if (leftarr.Length + 1 == kth)
    {
        //our pivot is the item we want
        return pivot;
    }
    else if (leftarr.Length >= kth)
    {
        // our item is in this array
        return getItem(leftarr, kth);
    }
    else
    {
        // need to look in the right array
        var rightarr = items.Where(s => s >= pivot).ToArray();
        return getItem(rightarr, kth - leftarr.Length);
    }
}
相关文章：