今日头条一面（估计是挂了）
问了一下笔试第一题中缀表达式你是怎么做的，然后只问了我一道题，如何求第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是否小于等于数组长度，代码就不加了，懂就好了。。。发出来发泄一下，顺便造福人类如果看到这个题不要像我这样死扣partition，然后就gg，不够总的来说其实还是我水平不够，高手估计5分钟就想出来了。#笔试题目##实习##内推##字节跳动#
投递快手等公司10个岗位 >