classSolution{public:intfirstMissingPositive(vector<int>& nums){// 假设有n个数，那么缺失的第一个正数一定在[1, n + 1]之间// 如果使用O(n)的额外空间，可以用哈希表先记录所有数，然后遍历[1, n+1]// 如果只用O(1)的额外空间；可以用nums本身作为哈希表，下标[0, size - 1]代表[1, size]// 如[3, 2, 5, 0]，遍历到3，将下标2置为负数；用负数代表该下标的数值存在，正数代表缺失// 这样只需再次遍历数组，第一个正数即答案// 注意<=0和>=n的数不处理int size = nums.size();for(int& i : nums){// 不处理if(i <=0) i = size +1;}// 第一次遍历for(auto i : nums){int abs_i =abs(i);if(abs_i <= size){nums[abs_i -1]=-abs(nums[abs_i -1]);// 置为负数}}// 第二次遍历for(int i =0; i < size;++i){if(nums[i]>0){return i +1;}}return size +1;}};
387. 字符串中的第一个唯一字符
387. 字符串中的第一个唯一字符
思路：哈希表记录每个字符的个数，然后再次遍历观察哪个字符个数为1
时间：O(n)；空间：O(字符种类数)
classSolution{public:intfirstUniqChar(string s){unordered_map<char,int>mp;for(auto c : s){mp[c]++;}int size = s.size();for(int i =0; i < size; i++){if(mp[s[i]]==1){return i;}}return-1;}};
