题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
思路
- 首先对数组进行排序。
2.若存在答案,必定为数组中间的元素。
3.将数组中间的元素取出,遍历数组记录下该数字出现的次数,若大于len/2则为正确答案,否则返回0。
Java代码实现
public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array.length == 0){ return 0; } Arrays.sort(array); int count = 0; int target = array[array.length/2]; for (int i = 0; i < array.length; i++) { if(array[i] == target){ count++; } } return count> array.length/2 ? target : 0; } }
Golang代码实现
func MoreThanHalfNum_Solution(nums []int)int{ if len(nums) == 0{ return 0 } sort.Ints(nums) target := nums[len(nums)/2] count := 0 for i:=0; i<len(nums);i++ { if nums[i] == target{ count++ } } if count>len(nums)/2{ return target } return 0 }