Number Appearing More Than Half the Time

1. Problem Description

An array contains a number that appears more than half the length of the array. Find this number. For example, in the length-9 array {1,2,3,2,2,2,5,4,2}, the number 2 appears five times, which is more than half the array length, so output 2. If no such number exists, output 0.

2. Approach

• Method 1: count with a Map. Time O(N), space O(N)
• Method 2: use quick sort. Time O(NlogN), space O(1)
• Method 3: count while traversing; +1 for the same number, otherwise -1. Time O(N), space O(1)

3. Implementation

3.1. Map Counting

• java

public class 数组中出现次数超过一半的数字
{
    public int MoreThanHalfNum_Solution(int[] array)
    {
        // Check parameters
        if (array == null || array.length == 0)
        {
            return 0;
        }

        // Traverse and place the counts into a map
        Map<Integer, Long> count = Arrays.stream(array).boxed().collect(Collectors.groupingBy(val -> val, Collectors.counting()));
        int halfLength = array.length >>> 1;
        for (Map.Entry<Integer, Long> entry : count.entrySet())
        {
            if (entry.getValue() > halfLength)
            {
                return entry.getKey();
            }
        }

        return 0;
    }
}

• go

// Time complexity: O(n)
// Space complexity: O(n)
func MoreThanHalfNum_Solution(numbers []int) int {
	if len(numbers) == 0 {
		return 0
	}

	count := make(map[int]int, 0)
	for _, number := range numbers {
		count[number]++
	}

	for key, val := range count {
		if val > len(numbers)/2 {
			return key
		}
	}

	return 0

}

3.2. Quick Sort

• java

public class 数组中出现次数超过一半的数字2
{
    public int MoreThanHalfNum_Solution(int[] array)
    {
        // Check parameters
        if (array == null || array.length == 0)
        {
            return 0;
        }

        // Sort first
        Arrays.sort(array);
        // The middle value may be the number that appears more than half the time
        int moreThanHalfNum = array[array.length >>> 1];
        // Verify at the end
        int count = 0;
        for (int val : array)
        {
            if (val == moreThanHalfNum)
            {
                count++;
            }
        }
        return count > array.length >>> 1 ? moreThanHalfNum : 0;
    }
}

• go

// Time complexity: O(nlogn)
// Space complexity: O(1)
func MoreThanHalfNum_Solution2(numbers []int) int {
	if len(numbers) == 0 {
		return 0
	}

	return 0
}

3.3. Same +1, Different -1

• java

public class 数组中出现次数超过一半的数字3
{
    public static void main(String[] args)
    {
        new 数组中出现次数超过一半的数字3().MoreThanHalfNum_Solution(new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2});
    }

    public int MoreThanHalfNum_Solution(int[] array)
    {
        // Check parameters
        if (array == null || array.length == 0)
        {
            return 0;
        }

        int length = array.length;
        int halfLength = array.length >>> 1;
        int val = array[0];
        int count = 1;
        // Traverse the array while counting: +1 if the next number equals the current candidate, otherwise -1
        for (int i = 1; i < length; i++)
        {
            if (array[i] == val)
            {
                count++;
            }
            else
            {
                count--;
                if (count == 0)
                {
                    val = array[i];
                    count = 1;
                }
            }
        }
        // Traverse the array once to verify
        count = 0;
        for (int num : array)
        {
            if (num == val)
            {
                count++;
            }
        }

        return count > halfLength ? val : 0;
    }
}

• go

// Count while traversing: +1 for the same number, otherwise -1
// Time complexity: O(n)
// Space complexity: O(1)
func MoreThanHalfNum_Solution3(numbers []int) int {
	if len(numbers) == 0 {
		return 0
	}

	val := numbers[0]
	count := 1
	for i := 1; i < len(numbers); i++ {
		if numbers[i] == val {
			count++
		} else {
			count--
			if count == 0 {
				val = numbers[i]
				count = 1
			}
		}
	}

	count = 0
	for _, number := range numbers {
		if number == val {
			count++
		}
	}

	if count > len(numbers)/2 {
		return val
	}
	return 0
}

4. References

• Majority Element - NowCoder
• Sword Offer 39. Majority Element - LeetCode