剑指offer面试题29 数组中出现次数超过一半的数字

考察点

数组

知识点

题目

分析
本题目要求数组中出现次数超过一半的数字，其实是需要有一点数学思维，遍历数组，假设第一个元素就是超过一半的元素，并且记录元素出现的次数times，当遇到跟他一样的元素的时候times服务器托管网++，不一服务器托管网样的时候times–，直到times=0的时候可以暂时说明这个元素出现的次数肯定不是超过一半的，超过一半的元素最终times一定是大于0的那个

public class TwentyNine {
	public static void main(String[] args) {
		int[] arr = {1,2,3,2,2,2,5,4,2};
		try {
			System.out.println(findMHalf(arr));
		} catch (Error e) {
			System.out.println(e);
		}
		int[] brr = {1,2,3,2,2,5,5,4};
		try {
			System.out.println(findMHalf(brr));
		} catch (Error e) {
			System.out.println(e);
		}
	}
	public static int findMHalf(int[] arr) {
		if (arr == null||arr.length  0) {
			throw new Error("input error");
		}
		int result = arr[0];
		int times = 1;
		for (int i = 1;iarr.length;i++) {
			if (result == arr[i]) {
				times++;
			} else if(times > 0) {
				times--;
			} else {
				result = arr[i];
				times = 1;
			}
		}
		int count = 0;
		for (int i = 0;iarr.length;i++) {
			if(result == arr[i]) {
				count++;
			}
		}
		if (count > arr.length/2) {
			return result;
		}
		throw new Error("input error");
	}
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 力扣题库第4题：移动零

题目内容： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 示例 : 输入: nums = [0,1,0,3,12] 输出服务器托管网: [1,3,12,0…