408算法题leetcode--第四天

41. 缺失的第一个正数

• 41. 缺失的第一个正数
• 思路：如代码，可以看官方题解
• 时间复杂度：O(n)；空间：O(1)

class Solution {
public:int firstMissingPositive(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(字符种类数)

class Solution {
public:int firstUniqChar(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;}
};