我实现了一种算法，解决了在未排序的数组中找到第k个最小元素的问题。我使用了堆结构，并依靠此公式优化了代码，
k1 = n-k + 1
k1是第k1个最大元素，因此我选择k和k1中的较小者。
不过，我无法通过在线判断传递时限错误。我不知道会不会有更多更好的复杂性，因为我必须创建一个不超过k大小的数组。可能小于k？或者，除了使用堆结构之外，还有另一种解决此问题的方法。
1
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
void minHeapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
if (l < n && arr[l] < arr[largest])
largest = l;
if (r < n && arr[r] < arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
minHeapify(arr, n, largest);
}
}
void maxHeapify(int arr[], int n, int i)
{
int smallest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
if (l < n && arr[l] > arr[smallest])
smallest = l;
if (r < n && arr[r] > arr[smallest])
smallest = r;
if (smallest != i) {
swap(arr[i], arr[smallest]);
maxHeapify(arr, n, smallest);
}
}
void buildMinHeap(int a[], int n) {
for (int i = n / 2; i >= 0; i--)
minHeapify(a, n, i);
}
void buildMaxHeap(int a[], int n) {
for (int i = n / 2; i >= 0; i--)
maxHeapify(a, n, i);
}
int kthsmallest(int minHeap[], int k, int n) {
int i, temp;
for (i = 0; i < k; i++)
cin >> minHeap[i];
buildMaxHeap(minHeap, k);
for (i = k; i < n; i++)
{
cin >> temp;
if (temp < minHeap[0])
{
minHeap[0] = temp;
maxHeapify(minHeap, k, 0);
}
}
return minHeap[0];
}
int kthlargest(int minHeap[], int k, int n) {
int i, temp;
for (i = 0; i < k; i++)
cin >> minHeap[i];
buildMinHeap(minHeap, k);
for (i = k; i < n; i++)
{
cin >> temp;
if (temp > minHeap[0])
{
minHeap[0] = temp;
minHeapify(minHeap, k, 0);
}
}
return minHeap[0];
}
int main() {//kth smallest element
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n, k, k1;
cin >> n >> k;
k1 = n - k + 1;//kth smallest element is the same as k1th largest element
if (k < k1) {
int *minHeap = new int[k];
cout << kthsmallest(minHeap, k, n);
}
else {
int *minHeap = new int[k1];
cout << kthlargest(minHeap, k1, n);
}
return 0;
}
请您是否可以帮助您找到更好的时间复杂度？
Problem：
查找数组的第k个最大元素
内存限制：256 MB
时间限制：1秒
输入：input.txt
输出：output.txt
任务：
您将得到n个整数和一个自然k的数组。
您必须找到数组的第k个最大元素。
您不能创建包含超过k个元素的数组。
输入：
第一行包含自然n（1≤n≤105）–
数组元素的数量和自然k。
第二行包含n个数字-数组的元素。
输出：
数组的第k个最大元素。
例：
Input | Output
-------------+-----------
6 2 | 7
7 4 6 3 9 1 |
最佳答案
时间复杂度是最佳的，但是您可以使代码效率更高：
不要使用递归，而是迭代解决方案
不要使用swap，而是在将子值复制到其父项时将原始值保留在内存中，并且仅在到达适当的插槽后才存储初始值。
不要执行两次2 * i：另一个子节点只是下一个。
让heapify函数采用一个额外的参数，该参数可以是索引i的当前值，也可以是其替换值。这样可以节省一个分配。
这是两个heapify函数的外观：
void minHeapify(int arr[], int n, int i, int key) { // add key as parameter
while (true) { // iterative
int child = 2 * i + 1; // do this only for left child, and limit number of variables
if (child+1 < n && arr[child] > arr[child+1]) // get child with least value
child++; // the right child is just one index further
if (child >= n || key <= arr[child]) break;
arr[i] = arr[child]; // don't swap, just copy child value to parent
i = child; // move down
}
arr[i] = key; // finally put the original value in the correct place
}
void maxHeapify(int arr[], int n, int i, int key) { // add key as parameter
while (true) { // iterative
int child = 2 * i + 1; // do this only for left child, and limit number of variables
if (child+1 < n && arr[child] < arr[child+1]) // get child with greatest value
child++; // the right child is just one index further
if (child >= n || key >= arr[child]) break;
arr[i] = arr[child]; // don't swap, just copy child value to parent
i = child; // move down
}
arr[i] = key; // finally put the original value in the correct place
}
void buildMinHeap(int a[], int n) {
for (int i = n / 2; i >= 0; i--)
minHeapify(a, n, i, a[i]); // pass a[i] also
}
void buildMaxHeap(int a[], int n) {
for (int i = n / 2; i >= 0; i--)
maxHeapify(a, n, i, a[i]); // pass a[i] also
}
int kthsmallest(int heap[], int k, int n) {
int i, temp;
for (i = 0; i < k; i++)
cin >> heap[i];
buildMaxHeap(heap, k);
for (i = k; i < n; i++) {
cin >> temp;
if (temp < heap[0])
maxHeapify(heap, k, 0, temp); // pass temp
}
return heap[0];
}
int kthlargest(int heap[], int k, int n) {
int i, temp;
for (i = 0; i < k; i++)
cin >> heap[i];
buildMinHeap(heap, k);
for (i = k; i < n; i++) {
cin >> temp;
if (temp > heap[0])
minHeapify(heap, k, 0, temp); // pass temp
}
return heap[0];
}
在main函数中，您可以对k == 1或k == n进行特殊处理，因此不需要堆，只需
min()或max()。一件奇怪的事是，您链接到的挑战说“第k个最大”，而说“第k个最小”。也许你混了。
因此，这是当作业要返回第k个最小值时的代码。但是请检查挑战，是否不应该对第k个最大的挑战进行挑战：
int main() {//kth smallest element
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n, k, k1;
cin >> n >> k;
k1 = n - k + 1;//kth smallest element is the same as k1th largest element
if (k == 1) {
int curr, next;
cin >> curr;
for (int i = 1; i < n; i++) {
cin >> next;
curr = min(curr, next);
}
cout << curr;
} else if (k1 == 1) {
int curr, next;
cin >> curr;
for (int i = 1; i < n; i++) {
cin >> next;
curr = max(curr, next);
}
cout << curr;
} else if (k < k1) {
int *heap = new int[k];
cout << kthsmallest(heap, k, n);
} else {
int *heap = new int[k1];
cout << kthlargest(heap, k1, n);
}
return 0;
}
关于c++ - 第K个最小元素-创建的数组不能超过k个大小，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59189376/