数组中出现次数超过一半的数字

1. 题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

2. 思路

• 第一种：使用Map统计。时间 O（N），空间 O（N）
• 第二种：使用快排。时间 O（NlogN），空间 O（1）
• 第三种：遍历的同时计数，相同的数+1，否则-1。时间 O（N），空间 O（1）

3. 实现

3.1. Map统计

• java

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

        //遍历计数放入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

//时间复杂度：O(n)
//空间复杂度：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. 快排

• java

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

        //先排序
        Arrays.sort(array);
        //中间的数可能是超过一半的数
        int moreThanHalfNum = array[array.length >>> 1];
        //最后验证一下
        int count = 0;
        for (int val : array)
        {
            if (val == moreThanHalfNum)
            {
                count++;
            }
        }
        return count > array.length >>> 1 ? moreThanHalfNum : 0;
    }
}

• go

//时间复杂度：O(nlogn)
//空间复杂度：O(1)
func MoreThanHalfNum_Solution2(numbers []int) int {
	if len(numbers) == 0 {
		return 0
	}

	return 0
}

3.3. 相同+1，不同-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)
    {
        //检查参数
        if (array == null || array.length == 0)
        {
            return 0;
        }

        int length = array.length;
        int halfLength = array.length >>> 1;
        int val = array[0];
        int count = 1;
        //遍历数组同时计数，如果下一个数与当前数相等，那么+1，否则-1
        for (int i = 1; i < length; i++)
        {
            if (array[i] == val)
            {
                count++;
            }
            else
            {
                count--;
                if (count == 0)
                {
                    val = array[i];
                    count = 1;
                }
            }
        }
        //遍历一次数组验证
        count = 0;
        for (int num : array)
        {
            if (num == val)
            {
                count++;
            }
        }

        return count > halfLength ? val : 0;
    }
}

• go

//遍历的同时计数，相同的数+1，否则-1
//时间复杂度：O(n)
//空间复杂度：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. 参考

• 数组中出现次数超过一半的数字_牛客网
• 剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣（LeetCode）