随机生成100维数组，利用分治策略求第K小元素选择问题。（C++）

在C++中，你可以使用随机数库`<random>`生成100维的数组，并通过分治算法（如快速选择算法）来解决第K小元素的选择问题。以下是简化的示例代码：

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

// 定义快速选择函数，返回数组中第k小的元素
int quickSelect(int arr[], int left, int right, int k) {
    if (left == right) return arr[left]; // 基线条件

    int pivotIndex = partition(arr, left, right); // 使用三数取中法找到基准位置
    if (k == pivotIndex) return arr[k]; // 如果k等于分区索引，直接返回基准值
    else if (k < pivotIndex) return quickSelect(arr, left, pivotIndex - 1, k); // 如果k在左侧递归查找
    else return quickSelect(arr, pivotIndex + 1, right, k); // 否则在右侧递归查找
}

// 三数取中法分区
int partition(int arr[], int left, int right) {
    std::random_device rd; // 使用随机设备获取随机数
    std::mt19937 gen(rd()); // 创建Mersenne Twister随机数生成器
    std::uniform_int_distribution<> dis(left, right); // 生成范围内的均匀分布随机数
    int pivotIndex = dis(gen);
    
    std::swap(arr[pivotIndex], arr[right]); // 将随机数作为基准放到最右边
    int i = left;
    for (int j = left; j < right; ++j) {
        if (arr[j] <= arr[right]) {
            std::swap(arr[i], arr[j]);
            i++;
        }
    }
    std::swap(arr[i], arr[right]);
    return i;
}

int main() {
    const int dim = 100;
    const int size = 1000000; // 数组大小
    int* arr = new int[size];
    std::vector<int> dims(dim, dim); // 初始化100维全零数组
    std::iota(dims.begin(), dims.end(), 0); // 将维度设置为从0开始的连续整数
    generateMultiDimensionalArray(arr, dims); // 生成100维随机数组
    
    int k;
    std::cout << "Enter the value of K: ";
    std::cin >> k;
    
    // 现在你可以调用quickSelect并传入你的数组、起始和结束索引以及k值
    int kthSmallest = quickSelect(arr, 0, size - 1, k - 1); // 注意这里k-1是因为下标从0开始计数
    std::cout << "The " << k << "th smallest element is: " << kthSmallest << std::endl;

    delete[] arr;
    return 0;
}

// 生成多维数组
void generateMultiDimensionalArray(int* arr, const std::vector<int>& dimensions) {
    for (int i = 0; i < dimensions[0]; ++i) {
        for (int j = 0; j < dimensions[1]; ++j) {
            // ... (继续嵌套循环直到所有维度)
            for (int d = dimensions.size() - 2; d >= 1; --d) {
                arr[i * dimensions[d] + j * dimensions[d - 1]] = rand(); // 生成随机数
            }
        }
    }
}