Created
November 1, 2023 15:43
-
-
Save hsuan1117/78935fb4dbe9bb8aa28e9af9fc19ac4f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <ctime> | |
#include <random> | |
double findMedian(std::vector<double> &arr, int l, int r) { | |
std::sort(arr.begin() + l, arr.begin() + r + 1); | |
int n = r - l + 1; | |
return arr[l + n / 2]; | |
} | |
double SELECT(std::vector<double> &arr, int l, int r, int k, int groupSize) { | |
if (l == r) { | |
return arr[l]; | |
} | |
int n = r - l + 1; | |
int numMedians = (n + groupSize - 1) / groupSize; | |
std::vector<double> medians(numMedians); | |
for (int i = 0; i < numMedians; i++) { | |
int groupEnd = std::min(l + (i + 1) * groupSize - 1, r); | |
medians[i] = findMedian(arr, l + i * groupSize, groupEnd); | |
} | |
double pivot = SELECT(medians, 0, numMedians - 1, numMedians / 2, groupSize); | |
int partitionIndex = | |
std::partition(arr.begin() + l, arr.begin() + r + 1, [pivot](double num) { return num < pivot; }) - | |
arr.begin(); | |
if (k == partitionIndex) { | |
return arr[k]; | |
} else if (k < partitionIndex) { | |
return SELECT(arr, l, partitionIndex - 1, k, groupSize); | |
} else { | |
return SELECT(arr, partitionIndex + 1, r, k, groupSize); | |
} | |
} | |
double randomizedSelect(std::vector<double> &arr, int l, int r, int k) { | |
std::random_device rd; | |
std::mt19937 gen(rd()); | |
std::uniform_int_distribution<> dis(l, r); | |
int pivotIndex = dis(gen); | |
std::swap(arr[pivotIndex], arr[r]); | |
int i = l; | |
for (int j = l; j <= r - 1; j++) { | |
if (arr[j] <= arr[r]) { | |
std::swap(arr[i], arr[j]); | |
i++; | |
} | |
} | |
std::swap(arr[i], arr[r]); | |
if (k == i) | |
return arr[i]; | |
if (k < i) | |
return randomizedSelect(arr, l, i - 1, k); | |
return randomizedSelect(arr, i + 1, r, k); | |
} | |
int main() { | |
std::ios::sync_with_stdio(true); | |
std::random_device rd; | |
std::mt19937 g(rd()); | |
int N, k, G; | |
std::cin >> N >> k >> G; | |
std::vector<double> arr(N); | |
for (int i = 0; i < N; i++) std::cin >> arr[i]; | |
double result = randomizedSelect(arr, 0, N - 1, k); | |
std::cout << result << '\n'; | |
// int k = N / 2; | |
// | |
// std::cout << "|---------|----------|--------------------|" << '\n' | |
// << "| Group | Time | result |" << '\n' | |
// << "|---------|----------|--------------------|" << '\n'; | |
// | |
// int test[4] = {3, 5, 7, 9}; | |
// for (int _n = 0; _n < 4; _n++) { | |
// double time = 0; | |
// std::vector<double> copied = arr; | |
// double result; | |
// for (int i = 0; i < 50; i++) { | |
// printf("| %d | %.2f | %02d/50 |\r", test[_n], (time / (double) i) / CLOCKS_PER_SEC, i); | |
// fflush(stdout); | |
// clock_t start = clock(); | |
// result = SELECT(copied, 0, N - 1, k, test[_n]); | |
// clock_t end = clock(); | |
// time += (end - start); | |
// } | |
// printf("| %d | %.2f | %d |\n", test[_n], (time / 50.0) / CLOCKS_PER_SEC, (int) result); | |
// } | |
// for (int _n = 0; _n < 1; _n++) { | |
// double time = 0; | |
// std::vector<double> copied = arr; | |
// double result; | |
// for (int i = 0; i < 50; i++) { | |
// printf("| random | %.2f | %02d/50 |\r", (time / (double) i) / CLOCKS_PER_SEC, i); | |
// fflush(stdout); | |
// clock_t start = clock(); | |
// result = randomizedSelect(copied, 0, N - 1, k); | |
// clock_t end = clock(); | |
// time += (end - start); | |
// } | |
// printf("| random | %.2f | %d |\n", (time / 50.0) / CLOCKS_PER_SEC, (int) result); | |
// } | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment