leetcode-169.求众数

 

题目:
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3] 输出: 3

示例 2:

输入: [2,2,1,1,1,2,2] 输出: 2

答案:

class Solution {// 众数求解算法public int majorityElement(int[] nums) {// 黑板(用于记录数据用)LinkedHashMap<Integer, Integer> blackboard = new LinkedHashMap<>();// 左边记录到的位置int leftPs = 0;// 右边记录到的位置int rightPs = nums.length - 1;// 众数Integer mode = null;tag: while (leftPs <= rightPs) {for (int i = leftPs; i <= rightPs; i++) {if (blackboard.get(nums[i]) == null) {blackboard.put(nums[i], 1);leftPs = i + 1;if (leftPs > rightPs) {mode = nums[i];}break;} else {int count = blackboard.get(nums[i]);count++;if (count>nums.length/2) {mode = nums[i];break tag;}blackboard.put(nums[i], count);}}for (int i = rightPs; i >= leftPs; i--) {if (blackboard.get(nums[i]) == null) {blackboard.put(nums[i], 1);rightPs = i - 1;if (rightPs < leftPs) {mode = nums[i];}break;} else {int count = blackboard.get(nums[i]);count++;if (count>nums.length/2) {mode = nums[i];break tag;}blackboard.put(nums[i], count);}}}return mode;} }

 

转载于:https://www.cnblogs.com/Grace-is-enough/p/9116016.html

总结

以上是生活随笔为你收集整理的leetcode-169.求众数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。