Majority Element 解答

Solution 1

Naive way

First, sort the array using Arrays.sort in Java. Than, scan once to find the majority element. Time complexity O(nlog(n))

 public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
Arrays.sort(nums);
int prev = nums[0];
int count = 1;
for (int i = 1; i < length; i++) {
if (nums[i] == prev) {
count++;
if (count > length / 2) return nums[i];
} else {
prev = nums[i];
count = 1;
}
}
return 0;
}
}

Solution 2

Since the majority always take more than a half space, the middle element is guaranteed to be the majority.

 public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
Arrays.sort(nums);
return nums[length / 2];
}
}

Solution 3 Moore voting algorithm

As we iterate the array, we look at the current element x:

  1. If the counter is 0, we set the current candidate to x and the counter to 1.
  2. If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.

After one pass, the current candidate is the majority element. Runtime complexity = O(n).

 public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
int maj = nums[0];
int count = 0;
for (int i = 0; i < length; i++) {
if (count == 0) {
maj = nums[i];
count = 1;
} else if (nums[i] == maj) {
count++;
} else {
count--;
}
}
return maj;
}
}

Solution 4 Bit Manipulation

We would need 32 iterations, each calculating the number of 1's for the ith bit of all n numbers. Since a majority must exist, therefore, either count of 1's > count of 0's or vice versa (but can never be equal). The majority number’s ith bit must be the one bit that has the greater count.

Time complexity: 32 * n = T(n)

 public class Solution {
public int majorityElement(int[] nums) {
int length = nums.length;
if (length == 1)
return nums[0];
int[] dig = new int[32];
for (int i = 0; i < length; i++) {
int tmp = nums[i];
for (int j = 0; j < 32; j++) {
dig[j] += tmp & 1;
tmp = tmp >> 1;
}
}
int max = 0;
int tmp = 1;
for (int i = 0; i < 32; i++) {
if (dig[i] > length / 2) {
max = max | tmp;
}
tmp = tmp << 1;
}
return max;
}
}
上一篇:LeetCode 226. Invert Binary Tree (反转二叉树)


下一篇:windows下编译qt的mysql驱动