只問了我一道題，如何求第k大并且不能改變原數組順序。。太久沒做題，腦子不太好使，面試官很nice，給了我提示，但是我還是沒當場想出來。。。后來我想了下，好像是記錄最大值和最小值，然后二分答案轉換為判斷問題，復雜度O（nlogn），額如果這個不是正解的話，感覺我也想不出其他解法了，記錄一下自己失敗經歷吧。。。。最后感謝老朋友的內推，是我自己不爭氣。

#include <cstdio> #include <ctime> #include <cstring> #include <random> #include <cmath> #include <stack> #include <vector> #include <queue> #include <map> #include <string> #include <algorithm> using namespace std; #define MAXN 15 #define MAXM 130 typedef long long LL; const int INF = 0x3f3f3f3f; int a[MAXN], n, k; int check(int mid){int sum = 0;for (int i = 0; i < n; i++){if (a[i] > mid){sum++;}}return sum + 1; } int main(){//freopen("input.txt", "r", stdin);scanf("%d%d", &n, &k);int minmum = INF, maxmum = -INF;for (int i = 0; i < n; i++){scanf("%d", &a[i]);minmum = min(minmum, a[i]);maxmum = max(maxmum, a[i]);}int ans;while (minmum <= maxmum){int mid = minmum + maxmum >> 1;if (check(mid)<=k){ans = mid;maxmum = mid - 1;}else{minmum = mid + 1;}}printf("%d\n", ans);//fclose(stdin); }

這里應該還要加特判k是否小于等于數組長度，代碼就不加了，懂就好了。。。

總結

以上是生活随笔為你收集整理的今日头条面试记录的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。