Mdr-C-Tutorial

主题

30404：有序统计选择 ​

题目 ​

使用分区在可修改数组中寻找排序后下标为 order 的元素。参数错误时数组和输出对象都不能改变；成功后允许数组被重排。

解析 ​

先验证 items、out_value、count 和 order，随后在当前半开区间中选取一个枢轴值，使用三路分区得到“小于、等于、大于”三个连续区域。若目标下标落在等于区域中即可返回，否则只在对应一侧继续分区。

三路分区能一次处理全部重复值。这里选中间位置作为枢轴，平均复杂度为 O(n)；固定枢轴在特殊输入上仍可能退化到 O(n2)。

答案 ​

c
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

static void swap_i64(int64_t *left, int64_t *right) {
    int64_t temporary = *left;
    *left = *right;
    *right = temporary;
}

bool select_kth_i64(
    int64_t *items,
    size_t count,
    size_t order,
    int64_t *out_value
) {
    if (count == 0 || order >= count || items == NULL ||
        out_value == NULL) {
        return false;
    }
    size_t left = 0;
    size_t right = count;
    while (left < right) {
        size_t pivot_index = left + (right - left) / 2;
        int64_t pivot = items[pivot_index];
        size_t less = left;
        size_t scan = left;
        size_t greater = right;
        while (scan < greater) {
            if (items[scan] < pivot) {
                swap_i64(&items[less], &items[scan]);
                ++less;
                ++scan;
            } else if (items[scan] > pivot) {
                --greater;
                swap_i64(&items[scan], &items[greater]);
            } else {
                ++scan;
            }
        }
        if (order < less) {
            right = less;
        } else if (order >= greater) {
            left = greater;
        } else {
            *out_value = pivot;
            return true;
        }
    }
    return false;
}

每轮只处理当前区间，平均时间复杂度为 O(n)，额外空间为 O(1)；最坏情况下枢轴划分极不平衡，会退化为 O(n2)。