谷歌NEXT program最后一题解法
如果分享题目不妥请删掉
今天谷歌NEXT program最后一题，题目大概是：
给出一个int数组，求出每一个元素的后面的元素中比它大且最小的元素。没有写-1。
int[] findNEXT(int[] num)
例如输入为 [11,13,10,5,12,21,3]
输出为 [12,21,12,12,-1,-1]
楼主只能想到要考虑重复……
#google##笔试题目#
2019-07-07 11:52 浙江大学 Java
关注
全部评论
算法才是灵魂
百度_核心搜索部rank_算法工程师
索引按值排序，维护索引递增栈。时间复杂度O(nlogn)代码如下，顺便说一下，楼主给的答案少了一个.. def nextProgram(l:list):
l = sorted(list(enumerate(l)), key=lambda x:x[1])
res = [-1] * len(l)
stack = []
for i,e in l:
while len(stack) > 0 and stack[-1] < i:
index = stack.pop()
res[index] = e
stack.append(i)
return res
print(nextProgram([11,13,10,5,12,21,3]))
#[12, 21, 12, 12, 21, -1, -1]
皮蛋烤柿粥
浙江大学 Java
vector<int> minCost(vector<int>& num) { vector<int> ans; map<int,int> m; for(int i=num.size()-1;i>=0;i--){ map<int,int>::iterator it=m.lower_bound(num[i]+1); if(it==m.end()){ ans.push_back(-1); } else{ ans.push_back(it->first); } m[num[i]]++; } reverse(ans.begin(),ans.end()); return ans; }
西安彭于晏
中国人民公安大学高级警官学院 C++
可以对索引按值排序然后维护一个递减的栈，也可以直接用cpp和java里面内置的数据结构
阿凡_
北京航空航天大学 算法工程师
vector<int> findNext(vector<int> A, int n) {
// write code here
map<int, int> m;
vector<int> result(n, -1);
for(int i = n - 1; i >= 0; i --){
for(auto item : m){
if(item.first > A[i]){
result[i] = item.first;
break;
}
}
m.insert({A[i], 1});
}
return result;
}
直接用STL自带的map(红黑树）就行了
相关推荐
