LeetCode : 169. Majority Element 众数 ゞ 浴缸里的玫瑰 2021-06-24 16:11 317阅读 0赞 **试题** Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: \[3,2,3\] Output: 3 Example 2: Input: \[2,2,1,1,1,2,2\] Output: 2 **代码** 随机加验证: class Solution { public int majorityElement(int[] nums) { Random rand = new Random(); int max = nums.length/2; while(true){ int can = nums[rand.nextInt(nums.length)]; if(valid(nums, can, max)){ return can; } } } public boolean valid(int[] nums, int can, int max){ int count = 0; for(int n: nums){ if(n==can) count++; if(count>max) return true; } return false; } } 消除法: class Solution { public int majorityElement(int[] nums) { int num=0,count=0; for(int n: nums){ if(count==0){ num = n; count++; continue; } if(n==num){ count++; }else{ count--; } } return num; } }
还没有评论,来说两句吧...