C-在巨大的2D阵列中找到第一个最大元素

Question

我正在尝试在大型2-D数组（约850,000个元素）中找到第n个最大元素。我现在使用的方法将其转换为1D数组，然后使用选择排序算法并以这种方式找到它，但需要太长。

任何人都知道找到第n个最大元素的好方法，而只是通过矩阵而不对其进行分类，就像找到最大元素一样。

Answer 1

我认为这是某种作业或面试问题，所以我只是为您制定步骤。

1. 找到一个适当的结构来存储n个节点。说X。（提示，快速搜索，插入，删除...）

2. 在one通行中穿过矩阵，保存比X中的矩阵大，然后将其保存到X中，并将最小值删除x。

3. 最后，x的最低最小值是最大的。

额外的空间是O(N)，时间为O(size of the matrix)。

Answer 2

我认为随机QuickSelect应该很好

https://en.wikipedia.org/wiki/quickselect

平均情况o（n）

Answer 3

除非您将数据结构更改为更好的数据结构（要么排序的数组或其他内容），否则您很难不迭代数组的所有元素。<<<<<<<<<<

来自此stackoverflow问题（在2D数组中打印最大数字 - 为什么我的代码打印三个数字）我得到了此代码并将其移至C语言：

#include<limits.h>

（...）

int twodArray[XXX][YYY];
int maxValue = INT_MIN;
int yForMaxValue, xForMaxValue;
int i = 0;
    for (i = 0; i < XXX; i++) {
        for (int j = 0; j < YYY; j++)
            if (twodArray[i][j] > maxValue) {
                maxValue = twodArray[i][j];
                yForMaxValue = j;
                xForMaxValue = i;
            }
        }
    }

yformaxvalue和yformaxValue是MaxValue位置的索引。

Answer 4

n尺寸有限的优先队列应完成工作。

将2D数组的每个元素放在队列中。
o（arraysize * log2（n））复杂性。
那么队列中的第一个元素是第n个最小（假设Arry size> = n）

#include <stdio.h>
#include <stdlib.h>
typedef int PriorityQueue_T;
typedef struct {
  PriorityQueue_T *A;
  size_t Length;
  size_t Size;
} PriorityQueue;
void PriorityQueue_Remove(PriorityQueue *Q) {
  if (Q->Length > 0) {
    size_t Index = 0;
    while (1) {
      size_t Mother = Index * 2 + 1;
      size_t Father = Mother + 1;
      if (Mother >= Q->Length) break;
      if ((Q->A[Mother] < Q->A[Father]) || (Father >= Q->Length)) {
        Q->A[Index] = Q->A[Mother];
        Index = Mother;
      } else {
        Q->A[Index] = Q->A[Father];
        Index = Father;
      }
    }
    Q->Length--;
    Q->A[Index] = Q->A[Q->Length];
    while (Index > 0) {
      size_t Child = (Index + 1)/ 2 - 1;
      if (Q->A[Index] >= Q->A[Child]) {
        break;
      }
      PriorityQueue_T tmp = Q->A[Index];
      Q->A[Index] = Q->A[Child];
      Q->A[Child] = tmp;
      Index = Child;
    }
  }
}
void PriorityQueue_Insert(PriorityQueue *Q, PriorityQueue_T x) {
   if (Q->Length < Q->Size || x > Q->A[0]) {
    if (Q->Length >= Q->Size) {
      PriorityQueue_Remove(Q);
    }
    size_t Index = Q->Length++;
    Q->A[Index] = x;
    while (Index > 0) {
      size_t Child = (Index + 1)/ 2 - 1;
      if (Q->A[Index] >= Q->A[Child]) {
        break;
      }
      PriorityQueue_T tmp = Q->A[Index];
      Q->A[Index] = Q->A[Child];
      Q->A[Child] = tmp;
      Index = Child;
    }
  }
}
// Pseudo code here to end
void PQ_FindNthSmallest(PriorityQueue_T Array[W][H], size_t N) {
  PriorityQueue Q;
  Q.Length = 0;
  Q.Size = N;
  Q.A = malloc(Q.Size * sizeof(PriorityQueue_T));
  For each element in the array
    PriorityQueue_Insert(&Q, Array[x][y]);
  printf("Nth smallest: %CorrespondingFormat", Q.A[0]);
  free(Q.A);
}