BiruLyu
6/18/2017 - 4:21 AM

## 169. Majority Element(Divide and Conquer).swift

``````
/*
1. Arrays.sort(nums) return nums[n/2];
2. Divide and Conquer
3. Majority Voting
*/
public class Solution {
public int majorityElement(int[] nums) {
if (nums == null || nums.length < 1) return 0;
int[] tuple = new int[2];
for (int num : nums) {
if (num == tuple[0]) {
tuple[1]++;
} else if (tuple[1] > 0) {
tuple[1]--;
} else {
tuple[0] = num;
}
}
return tuple[0];
}
}``````
``````class Solution {
func majorityElement(_ nums: [Int]) -> Int {
if nums.count == 0 {
return 0
}

return helper(nums, 0, nums.count - 1)
}

private func helper(_ nums: [Int], _ left: Int, _ right: Int) -> Int {
if left == right {
return nums[left]
}

let middle = left + ((right - left) >> 1)
let leftMiddle = helper(nums, left, middle)
let rightMiddle = helper(nums, middle + 1, right)

if leftMiddle == rightMiddle {
return leftMiddle
}

var leftCount = 0
var rightCount = 0

for i in left...right {
if nums[i] == leftMiddle {
leftCount += 1
} else if nums[i] == rightMiddle {
rightCount += 1
}
}

return leftCount > rightCount ? leftMiddle : rightMiddle
}
}``````