记一道面试题～ （整个就一大无语）
事情是这样的，今天面试了富途，面试官问了一些八股之后出了两道题，第一题是这个 https://leetcode.cn/problems/can-make-arithmetic-progression-from-sequence/
so easy啊
但是，面试官紧接着又说要求用时间复杂度O(n)的解法
那就意味着，一切先排序的解法直接pass掉了
我苦思冥想，是真没想到有啥O(n)的解法
只能先跳过这题，做另一道
面试结束后我在leetcode找到了这个题，一看题解也全是先排序的解法
所以O(n)的解法到底是什么？？？
经过我一顿骚操作，终于在第10次提交时过了这道题
然而，我觉得这道题还没完，说不定只是leetcode后台case太少才通过的
以下是代码：
class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
int Max = arr[0];
int Min = arr[0];
int sum =0;
int len = arr.size();
unordered_map<int,int> mp;
for (int i=0;i<len;++i){
mp[arr[i]]++;
Min = min(arr[i],Min);
Max = max(arr[i],Max);
sum+=arr[i];
}
if ((Max+Min)*len/2!=sum) return false;
if ((Max-Min) % (len-1)!=0) return false;
int step = (Max-Min) / (len-1);
if (step == 0) return true;
for (int i=1;i<len;++i){
if (mp[arr[i]]>1) return false;
if ((arr[i]-arr[i-1])%step!=0) return false;
}
return true;
}
}; 欢迎各路大佬指教！！！
#富途##C/C++#
查看5道真题和解析