In this Leetcode Majority Element II problem solution, you are given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Problem solution in Python.
import collections class Solution: def majorityElement(self, nums): length = len(nums) counter = collections.Counter(nums) if length<3: return counter.keys() result = [] words = counter.most_common(3) for i in range(0,min(3,len(counter))): if words[i][-1]>length/3: result.append(words[i][0]) return result
Problem solution in Java.
public List<Integer> majorityElement(int[] nums) { List<Integer> result = new ArrayList<>(); if(nums.length < 3){ int n = nums.length; for(int i=0; i<n; i++){ if(!result.contains(nums[i])) result.add(nums[i]); } return result; } Arrays.sort(nums); int count=1; int gt = nums.length/3; for(int i=0; i<nums.length-1; i++){ if(nums[i] == nums[i+1]){ count++; } if(count > 1 && nums[i] != nums[i+1]){ count = 1; } if(count >= gt+1){ if(!result.contains(nums[i])){ result.add(nums[i]); count = 1; } } } return result; }
Problem solution in C++.
vector<int> majorityElement(vector<int>& nums) { vector<int> vec; int n= floor(nums.size()/3)+1; map<int,int> mp; map<int,int>::iterator it; for(int i=0;i<nums.size();i++){ it=mp.find(nums[i]); if(it==mp.end()) mp.insert(pair<int,int>(nums[i],1)); else it->second=mp[nums[i]]+1; } for(it=mp.begin();it!=mp.end();it++){ if(it->second>=n) vec.push_back(it->first); } return vec; }
Problem solution in C.
void add_back(int **ret, int *rS, int num){ *ret = realloc(*ret, sizeof(int) * (*rS + 1)); (*ret)[*rS] = num; *rS += 1; return; } int* majorityElement(int* nums, int numsSize, int* returnSize){ *returnSize = 0; if(nums == NULL || numsSize < 1) return NULL; int cand1, cand2, count1, count2; cand1 = cand2 = count1 = count2 = 0; for (int i = 0; i < numsSize; i++) { int num = nums[i]; if (cand1 == num) { count1++; }else if (cand2 == num) { count2++; }else if (count1 == 0) { cand1 = num; count1++; }else if (count2 == 0) { cand2 = num; count2++; }else { count1--; count2--; } } count1 = count2 = 0; for (int i = 0; i < numsSize; i++) { int num = nums[i]; if (cand1 == num) count1++; else if (cand2 == num) count2++; } int *ret = NULL; if(count1 > numsSize/3) add_back(&ret, returnSize, cand1); if(count2 > numsSize/3) add_back(&ret, returnSize, cand2); return ret; }
0 Comments