hashtbale

题目49

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

思路：哈希表，对排序后的单词作为索引。

c++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>>res;
        map<string,vector<string>>cur;
        for(auto str:strs)
        {
            string s=str;
            sort(s.begin(),s.end());
            cur[s].push_back(str);
        }
        for(auto it=cur.begin();it!=cur.end();it++)
            res.push_back(it->second);
       return res;
    }
};

题目169

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

c++

public:
    int majorityElement(vector<int>& nums) {
        map<int,int>res;
        int max=0,ans=0;
        for(int i=0;i<nums.size();i++)
        {
                res[nums[i]]++;
            if(res[nums[i]]>max)
            {
                max= res[nums[i]];
                ans=nums[i];
            }
            
        }
       
        return ans;
    }
};

方法二:因为出现最多的数出现超过了一半，所以随机选一个会很大概率是他

c++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        while (true) {
            int candidate = nums[rand() % nums.size()];
            int count = 0;
            for (int num : nums)
                if (num == candidate)
                    ++count;
            if (count > nums.size() / 2)
                return candidate;
        }
        return -1;
    }
};