给你一个长度为 n 的数组,其中只有一个数字出现了大于 n/2 次,问如何快速找到这个数字。
第一种写法
public int find(int[] nums) { int count = 1; int result = nums[0]; for (int i = 1; i < nums.length; i++) { count = result == nums[i] ? ++count : --count; if (count == 0) { result = nums[i + 1]; } } return result; }
第二种写法
public int find(int[] nums) { int result = nums[0], count = 0; for (int i = 0; i < nums.length; i++) { if (result == nums[i]) { count++; } else { count--; } if (count == 0) { result = nums[i]; count = 1; } } return result; }
摩尔投票算法
摩尔投票算法是用于找出数组中出现次数超过n/2的元素,其核心思想在于遍历过程中不同元素之间两两抵消,由于一个数组中,出现次数超过n/2最多只有一个,那么遍历结束时,未被抵消掉的即是出现次数超过n/2的元素。
数学思想
众数一定比其他所有的数加起来的数量要多,就算是众数与其他每一个数相抵消,最后剩下来的也是众数。
扑克牌抽象算法
假如有9张扑克牌( 8,8,8,7,8,4,2,8,2),依次抓牌,手里抓两张牌,比较两张牌是否一样。不一样就把两张牌放下,一样就放手里继续抓牌。手里没有牌继续抓两张牌比较。手里有牌继续抓一张牌比较如果和手里牌相同就留下,不同就拿出两张不同的牌。你会发现手里最后剩余的就是 8。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)