首页 > 代码库 > LeetCode 169. Majority Element解题方法
LeetCode 169. Majority Element解题方法
题目：
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.
也就是找数组中出现次数大于一半的数字，题目保证这个数字存在。
方法一：位操作
针对数组中每一个数的每一位，计算每一位上0和1出现的次数，取出现多的作为最终数字的当前位。
代码如下：时间复杂度32n=O(n)，空间复杂度O(1)
// bit操作 public int majorityElement(int[] nums) { int temp = 0, ans = 0, count0 = 0, count1 = 0; for (int i = 0; i < 32; i++) { count0 = 0; count1 = 0; for (int j = 0; j < nums.length; j++) { if (((nums[j] >>> i) & 1) == 1) count1++; else count0++; } if (count1 > count0) temp += 1; if (i < 31) temp >>>= 1; } for (int i = 0; i < 32; i++) { ans += ((temp >> i) & 1); if (i < 31) ans <<= 1; } return temp; }
方法二：HashMap，
空间复杂度O(n),时间复杂度O(n),相对位操作更耗时。
// 使用hashMap public int majorityElement(int[] nums) { int temp = 0, ans = 0, count0 = 0, count1 = 0; Map<Integer, Integer> countMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1); if (countMap.get(nums[i]) > nums.length / 2) return nums[i]; } return 0; }
方法三：计数法，
这个方法应该是最优解法吧。相比位操作更好。
该方法的思路是从局部思考问题，前2K个数字中，某个数无法做成majority element，但它也有可能出现很多次，但是最终在某个点上会被其他不相同的数字中和了。从后面再计数。最终找到的就是majority element。（描述的不好，直接看代码理解吧）。
假设被中和的是majority element，不用担心，因为你干掉了和你一样多的对手，在后续的子数组中，你还是大头。
假设被中和的不是，那么后续子数组中，你还是不能。
代码如下：
public int majorityElement(int[] nums) { int count = 0; int ans = nums[0]; for (int i : nums) { if (count == 0) ans = nums[i]; if (ans == nums[i]) count++; else count--; } return ans; }
LeetCode 169. Majority Element解题方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。