有人可以解释一下这个 "kth smallest integer in an unsorted array"代码吗？ - C

Question

我基本上必须编写一个函数，它接受一个数组、一个表示数组中元素的 int n 和一个表示数组中第 k 个最小 int 的 int k (不是第 k 个最小位置)。不允许修改(排序)数组。我花了一段时间试图弄清楚这个解决方案，但我一直让自己感到困惑。

有人可以尝试向我解释一下吗？谢谢!

int
kth_smallest(int A[], int n, int k) {
    int i, j;
    int smaller, equal;

    for (i = 0; i < n; i++) {
        smaller = 0;
        equal = 0;
        for (j = 0; j < n; j++) {
            smaller += (A[j] < A[i]);
            equal += (A[j] == A[i]);
        }
        if (smaller <= k && k < smaller + equal) {
            return A[i];
        }
    }
    printf("No %d'th smallest possible in array of %d items\n", k, n);
    exit(EXIT_FAILURE);
}

这是我针对一些测试数据计算的步出解决方案。

A[4] = {1,1,4,3} | n = 4 | k = 3 | Expected outcome = 4

    Loop 1 (A[i] = 1) :
    smaller = 0.
    equal   = 2.

    test: smaller <= k && k < smaller+equal | 0 <= 3 && 3 < 2 | FALSE

    Loop 2 (A[i] = 1):
    smaller = 0.
    equal   = 2.

    test: smaller <= k && k < smaller+equal | 0 <= 3 && 3 < 2 | FALSE

    Loop 3 (A[i] = 4):
    smaller = 3.
    equal   = 1.

    test: smaller <= k && k < smaller+equal | 3 <= 3 && 3 < 4 | TRUE

    RETURN A[i] (=4). (Which matches expected)

    Third smallest int in A is 4, with 1 and 3 before it.

Answer 1

提示:在理解此类算法时，首先考虑基本(和极端)情况通常会很有帮助。首先假设数组中的所有元素都是不同的。然后，当您到达 'if' 子句时，'smaller' = 小于当前检查元素 (A[i]) 的元素数，并且 'equal' = 1。因此 'if' 子句变为:

if (smaller <= k && k < smaller + 1)

这必然意味着

smaller = k

因此，通过返回 A[i]，您将返回数组中具有 (k-1) 个较小元素的元素(因为“k”是基于 0 的索引)，即第 k 个最小元素，如预期的那样。现在看一个所有元素都相等的示例。较小 = 0 且等于 = n(始终)。因此 0..n-1 范围内的任何“k”都将返回数组中的单个数字，再次如预期。现在再次考虑你的例子，看看你是否能更好地理解它。祝你好运!