给定一个数列a1,a2,a3,...,an和m个三元组表示的查询,对于每个查询(i,j,k),输出ai,ai+1,...,aj的升序排列中第k个数。
#include <iostream> using namespace std; #define SIZE 20 #define M 3 typedef struct Elem { int i, j; int k; } ELEM; /* 表示一个元素的三元组结构 */ int getMedian(int* arr, int low, int high) { int mid = low + ((high - low) >> 1); if (arr[mid] > arr[high]) { swap(arr[mid], arr[high]); } if (arr[low] > arr[high]) { swap(arr[low], arr[high]); } if (arr[mid] > arr[low]) { swap(arr[low], arr[mid]); } return arr[low]; } int findThMin(int* arr, int low, int high, int k) { int pivot = getMedian(arr, low, high); int lowTmp = low; int highTmp = high; while (lowTmp < highTmp) { while (lowTmp < highTmp && arr[highTmp] > pivot) { highTmp--; } arr[lowTmp] = arr[highTmp]; while (lowTmp < highTmp && arr[lowTmp] < pivot) { lowTmp++; } arr[highTmp] = arr[lowTmp]; } arr[lowTmp] = pivot; if (k == lowTmp) { return arr[lowTmp]; } else if (k < lowTmp) { return findThMin(arr, low, lowTmp - 1, k); } else { return findThMin(arr, lowTmp + 1, high, k); } } int* getSubArray(int* arr, int begin, int end) { int* tmp = new int[end - begin + 1]; for (int i = 0, j = begin; j <= end; ++i, j++) { tmp[i] = arr[j]; } return tmp; } int main() { Elem* elem = new Elem(); elem->i = 4; elem->j = 9; elem->k = 3; Elem* elem2 = new Elem(); elem2->i = 2; elem2->j = 8; elem2->k = 6; Elem* elem3 = new Elem(); elem3->i = 1; elem3->j = 6; elem3->k = 5; Elem *elems[M] = { elem, elem2, elem3 }; int* arr = new int[SIZE]; srand(unsigned(time(0))); for (int i = 0; i < SIZE; i++) { arr[i] = rand() * RAND_MAX + rand(); } for (int i = 0; i < M; ++i) { // cout << elems[i]->k << endl; //获取指定子数组 int* tmp = getSubArray(arr, elems[i]->i - 1, elems[i]->j - 1); /*cout << "before data set:" << endl; for (int k = 0; k <= elems[i]->j - elems[i]->i; ++k) { cout << tmp[k] << endl; }*/ //在规定的数组内取得第几个最小的元素 int data = findThMin(tmp, 0, elems[i]->j - elems[i]->i, elems[i]->k - 1); cout << elems[i]->k << " th min data:" << data << endl; cout << "after data set:" << endl; for (int k = 0; k <= elems[i]->j - elems[i]->i; ++k) { cout << tmp[k] << endl; } } return 0; }