LeetCode/go/majority-element.go

package main

import (
	rand "math/rand/v2"
)

func majorityElement(nums []int) int {
	DISCARD := -1_000_000_001

	threshold := len(nums) >> 1
	for {
		sample := nums[rand.N(len(nums))]
		if sample == DISCARD {
			continue
		}

		counter := 0
		for i, x := range nums {
			if x == sample {
				counter++
				nums[i] = DISCARD
			}

			if counter > threshold {
				return sample
			}
		}
	}
}