leetcode 最长定差子序列 -- Map
2019-10-08 本文已影响0人
夏liao夏天
给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。
示例1
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。
示例2
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。
示例3
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。
提示：
- 1 <= arr.length <= 10^5
- -10^4 <= arr[i], difference <= 10^4
该题需要注意的地方为：
- 要按照数组本来的顺序，不能对数组进行排序操作
在解题时，我自己的想法是外面一个循环，里面再从当前元素出发，寻找当前元素的等差数列，虽然有对使用过的元素进行标记，不再循环，但是依然是将近O(n*n)的复杂度。我朋友的想法就是使用Map数组来存储每个元素的等差数列长度，只需要一层循环，在循环时，查找Map数组中是否有当前元素的前一项，如果有，取出前一项的等差数列的长度，将这个长度加1就是当前元素的等差数列的长度。最后只需要找出Map数组中等差数列长度的最大值了。由于Map数组查找的算法复杂度为O(logn)，因此总体的算法复杂度为O(nlogn)。
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
map<int,int> storeMap;
for(int i=0;i<arr.size();i++){
int preValue = arr[i] - difference;
auto iter = storeMap.find(preValue);
if(iter != storeMap.end()){
auto iter2 = storeMap.find(arr[i]);
if(iter2 != storeMap.end()){
iter2->second = iter->second+1;
}
else{
storeMap.insert(pair<int,int>(arr[i], iter->second + 1));
}
}
else{
storeMap.insert(pair<int,int>(arr[i], 1));
}
}
int max_len = 1;
for(auto iter=storeMap.begin();iter!=storeMap.end();iter++){
if(iter->second > max_len){
max_len = iter->second;
}
}
return max_len;
}
};
