In this Leetcode Majority Element problem solution we have Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Problem solution in Python.
class Solution(object): def majorityElement(self, nums): candi, count = 0, 0 for num in nums: if count == 0: candi = num count += 1 elif num == candi: count += 1 else: count -= 1 return candi
Problem solution in Java.
public int majorityElement1(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num: nums) { if (map.containsKey(num)) map.put(num, map.get(num) + 1); else map.put(num, 1); if (map.containsKey(num) && map.get(num) > nums.length/2) return num; } return -1; } public int majorityElement2(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } public int majorityElement(int[] nums) { int majority = 0; int count = 0; for (int num: nums) { if (count == 0) majority = num; if (num == majority) count ++; else count--; } return majority; }
Problem solution in C++.
class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int, int> myMap; int n = nums.size(); int index = 0, i; unordered_map<int, int>::const_iterator got; for(i=0; i<n; i++) { got = myMap.find(nums[i]); if(got == myMap.end()) { myMap.insert({nums[i], index}); index++; } } vector<int> count(index, 0); for(i=0; i<n; i++) count[myMap[nums[i]]]++; int max = 0, maxIndex=0; for(i=0; i<index; i++) if(count[i]>max) { max = count[i]; maxIndex = i; } for(i=0; i<n; i++) if(myMap[nums[i]] == maxIndex) return nums[i]; } };
Problem solution in C.
int majorityElement(int* nums, int numsSize){ int major=0,c=1,i; int n=numsSize; for(i=1;i<n;i++) { if (nums[major]==nums[i]){ c++; } else c--; if (c==0) { major=i; c=1; } } return nums[major]; }
0 Comments