谷歌NEXT program最后一题解法

如果分享题目不妥请删掉

今天谷歌NEXT program最后一题,题目大概是:

给出一个int数组,求出每一个元素的后面的元素中比它大且最小的元素。没有写-1。

int[] findNEXT(int[] num)

例如输入为 [11,13,10,5,12,21,3]

输出为 [12,21,12,12,-1,-1]


楼主只能想到要考虑重复……
#google##笔试题目#
全部评论
索引按值排序,维护索引递增栈。时间复杂度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]
2 回复
分享
发布于 2019-07-07 14:57
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(红黑树)就行了
点赞 回复
分享
发布于 2019-07-07 12:48
秋招专场
校招火热招聘中
官网直投
可以对索引按值排序然后维护一个递减的栈,也可以直接用cpp和java里面内置的数据结构
点赞 回复
分享
发布于 2019-07-07 13:33
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; }
点赞 回复
分享
发布于 2020-03-01 20:11

相关推荐

点赞 12 评论
分享
牛客网
牛客企业服务