169. Majority Element
Last updated
Last updated
/**
* Time complexity : O(n^2). The brute force algorithm contains two
* nested for loops that each run for nn iterations, adding up to
* quadratic time complexity.
* Space complexity : O(1). The brute force solution does not allocate
* additional space proportional to the input size.
*/
class Solution {
public int majorityElement(int[] nums) {
int majorityCount = nums.length/2;
for (int num : nums) {
int count = 0;
for (int elem : nums) {
if (elem == num) {
count += 1;
}
}
if (count > majorityCount) {
return num;
}
}
return -1;
}
}/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
}
else {
counts.put(num, counts.get(num)+1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = countNums(nums);
Map.Entry<Integer, Integer> majorityEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (majorityEntry == null ||
entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}
return majorityEntry.getKey();
}
}/**
* Time complexity : O(nlgn). Sorting the array costs O(nlgn) time in Python
* and Java, so it dominates the overall runtime.
* Space complexity : O(1) or (O(n)). We sorted nums in place here - if that
* is not allowed, then we must spend linear additional space on a copy
* of nums and sort the copy instead.
*/
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}/**
* Time complexity : O(n). Boyer-Moore performs constant work exactly n
* times, so the algorithm runs in linear time.
* Space complexity : O(1). Boyer-Moore allocates only constant additional memory.
*/
class Solution {
public int majorityElement(int[] nums) {
int result = 0, count = 0;
for(int n: nums) {
if(count == 0) {
result = n;
count = 1;
} else if(result == n) {
count++;
} else {
count--;
}
}
return result;
}
}