c#数组次序统计系列1

题目

未排序数组中的第 K 个最小/最大元素

Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 3
Output: 7

方法1

1、按升序对输入数组进行排序
2、返回排序数组中 K-1 索引处的元素（基于 0 的索引）

方法2

 public static void Main()
    {
 
        int[] arr = { 12, 3, 5, 7, 19 };
        int N = arr.Length;
        int K = 4;
 
        SortedSet s = new SortedSet();
        foreach(int i in arr) s.Add(i);
 
        foreach(int itr in s)
        {
            if (K == 1) {
                Console.WriteLine(itr);
                // itr is the kth element in the set
                break;
            }
            K--;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法3

1、将所有数组元素插入最小堆
2、调用 extractMin() 函数 K 次
3、返回最后一次调用 extractMin() 函数得到的值

方法4

1、构建给定数组的前 K 个元素（arr[0] 到 arr[K-1]）的 Max-Heap MH。

2、对于每个元素，在第 K 个元素之后（arr[K] 到 arr[n-1]），将其与 MH 的根进行比较。

• 如果元素小于根，则将其设为根并为 Max-Heap MH 调用 heapify
• 否则忽略它。

3、最后，MH 的根是第 K 个最小的元素。

方法5

对输入数组运行快速排序算法
1、在这个算法中，选择一个枢轴元素并将其移动到正确的位置
2、现在，如果枢轴的索引等于K，则返回该值，否则如果枢轴的索引大于K，则对左子数组递归，否则对右子数组递归
3、重复此过程，直到找不到索引 K 处的元素