Swift solution - Divide and Conquer


  • 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
        }
    }
    

  • 0
    K

    @cloud.runner ,it may work for all scenarios, But, if you try with custom case [1,2,3,4,5,6] . It will fail.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.