活跃农民
- 积分
- 420
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-7-28
- 最后登录
- 1970-1-1
|
- // O(k*N) time, O(k) space, here k = 4
- vector<int> majorityElements(vector<int>& nums, int k = 4) {
- int n = nums.size();
- vector<int> ans;
- vector<int> cand(k, 0), freq(k, 0);
- iota(cand.begin(), cand.end(), 0);
- for(int num : nums) {
- bool match = false; // check if there is a match with existing candidate
- for(int i = 0; i < k; i++) {
- if(num == cand[i]) {
- freq[i]++;
- match = true;
- break;
- }
- }
- if(!match) { // no match with existing candidate
- for(int i = 0; i < k; i++) {
- if(freq[i] == 0) { // we can replace with num a candidate with freq = 0
- freq[i] = 1;
- cand[i] = num;
- break;
- }
- if(i == k) { // no match and no replacement
- for(int i = 0; i < k; i++) freq[i]--; // freq[] all reduce by 1
- }
- }
- }
- }
- for(int c : cand) {
- if(count(nums.begin(), nums.end(), c) >= ceil(n/4))
- ans.push_back(c); // if c is with freq > n/4;
- }
- return ans;
- }
- // O(logN) time, O(1) space
- // only need to check if nums at indices n/4-1, 2*n/4-1, 3*n/4-1, n-1 are qualified candidate.
- vector<int> majorityElementsBinarySearch(vector<int>& nums) {
- unordered_set<int> cand;
- int n = nums.size();
- cand.insert(nums[n/4-1]);
- cand.insert(nums[2*n/4-1]);
- cand.insert(nums[3*n/4-1]);
- cand.insert(nums[n-1]);
- vector<int> ans;
- for(int c : cand) {
- int range = upper_bound(nums.begin(), nums.end(), c) - lower_bound(nums.begin(), nums.end(), c);
- if(range >= n/4) ans.push_back(c);
- }
- return ans;
- }
- int main(int argc, const char * argv[]) {
- // insert code here...
- vector<int> nums1 = {1,1,2,2,3,3,4,4};
- auto ans = majorityElements(nums1);
- for(int i : ans) cout << i << " ";
- cout << endl;
-
- vector<int> nums2 = vector<int>({0,1,1,1,2,2,3,3,3,4,4,5});
- ans = majorityElements(nums2);
- for(int i : ans) cout << i << " ";
- cout << endl;
-
- ans = majorityElementsBinarySearch(nums1);
- for(int i : ans) cout << i << " ";
- cout << endl;
-
- ans = majorityElementsBinarySearch(nums2);
- for(int i : ans) cout << i << " ";
- cout << endl;
- return 0;
- }
复制代码 |
|