设计公司网站的主页怎么做_网站建设公司找博行_百度网页_如何写软文推广产品

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

**进阶：**尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

方法1 Hash表法

class Solution {public int majorityElement(int[] nums) {HashMap<Integer,Integer> map = new HashMap<>();// 向hash表中存放数据for(int num: nums) {if(map.containsKey(num)){map.put(num,map.get(num)+1);}else {map.put(num,1);}}// 遍历hash表求解value最大值的keyint  cnt = Integer.MIN_VALUE;int maxNum = nums[0];for(int num:map.keySet()){if(cnt < map.get(num)){maxNum = num;cnt = map.get(num);}}return maxNum;}}

方法2 概率法

class Solution {public int majorityElement(int[] nums) {Random r = new Random();for (int i = 0; i < 10; i++) {int index = r.nextInt(nums.length);if(isMajor(nums,index)) {return nums[index];}}return -1;}public boolean isMajor(int[] nums ,int index ) {int  cnt = 0 ;int  halfLen = nums.length/2;for (int num: nums) {cnt ++;if (cnt > halfLen) {return true;}}return false;}}

169. 多数元素 - 力扣（LeetCode）