reading note 2

本文主要是介绍reading note 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//longest consecutive sequence
//given an unsorted array of integers, find the length of the longest 
//consecutive elements sequence. 
//先排序，然后求解时间复杂度o(nlogn)
//your algorithm should be run in o(n) complexity==>哈希表
//space complexity o(n)
int longestconsecutive(const vector<int>& nums){
unordered_map<int,bool> used;
for(auto i : nums) used[i] = false;
int longest = 0;
for(auto i : nums){
if(used[i]) continue;
int length = 1;
used[i] = true;
for(int j = i + 1; used.find(j) != used.end(); ++j){
used[j] = true;
++length;
}
for(int j = i - 1; used.find(j) != used.end(); --j){
used[j] = true;
++length;
}
longest = max(longest, length);
}
return longest;
}
//longest consecutive sequence
//time complexity o(n) space complexity o(n)
int longestconsecutive(vector<int>& nums){
unordered_map<int, int> map;
int size = nums.size();
int l = 1;
for(i = 0;i < size; i++){
if(map.find(nums[i]) != map.end()) continue;
map[nums[i]] = 1;
if(map.find(nums[i] - 1) != map.end()){
l = max(l,mergecluster(map,nums[i] - 1,nums[i]));
}
if(map.find(nums[i] + 1) != map.end()){
l = max(l,mergecluster(map,nums[i],nums[i] + 1));
}
}
return size == 0 ? 0 : 1;
}


int mergecluster(unordered_map<int,int>& map, int left, int right){
int upper = right + map[right] - 1;
int lower = left - map[left] + 1;
int length = upper - lower + 1;
map[upper] = length;
map[lower] = length;
return length;
}


// given an array of integers, find two numbers such that they add up to a 
//specific target number, the function twosum should return indices of the 
//two numbers such that they add up to the target, where index1 must be less
//than index2, please note that your returned answers(both index1 and index2)
//are not zero-based
//you may assume that each input would have exactly one solution
//方法1:暴力,复杂度o(n^2),超时
//方法2:hash,用一个哈希表，存储每个数对应的下标，复杂度o(n);
//time complexity o(n) space complexity o(n)
vector<int> twosum(vector<int>& nums, int target){
unordered_map<int,int> mapping;
vector<int> result;
for(int i=0; i < nums.size();i++){
mapping[nums[i]] = i;
} 
for(int i=0;i < nums.size();i++){
const int gap = target - nums[i];
if(mapping.find(gap) != mapping.end() && mapping[gap] > i){
result.push_back(i+1);
result.push_back(mapping[gap]+1);
break;
}
}
return result;
}

这篇关于reading note 2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---