leetcode每日计算题（leetCode169题多数元素）

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

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

示例：

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

2.解题过程2.1 第一个思路：首先的一个想法是针对每一个元素统计出现次数，然后取次数最多的元素记下来，代码如下：

public int majorityElement(int[] nums) { int maxNum = 0; //记录最大次数 int target = 0; //记录目标值 for(int i = 0; i<nums.length;i ){ int tmp = nums[i]; int num = 0; for (int j = 0; j < nums.length; j ) { if(nums[j] == tmp){ num ; } } if(num > maxNum){ //如果次数出现了新高，则更新最大次数和目标值 target = tmp; maxNum = num; } } return target; }

分析：算法的时间复杂度是O(n*n),空间复杂度是常量O(1)；

改进之处：可以把nums.length用一个变量抽取出来

2.2 第二个思路：利用HsahMap只遍历一次，从而降低时间复杂度，代码如下：

public int majorityElement1(int[] nums) { int target = -1; //目标值 int length = nums.length; HashMap<Integer,Integer> hashMap = new HashMap(length/2); //hashMap的容量尽量初始化，避免多次扩容。（初始规则：初始值 = 计划实体数 / 0.75） for(int i = 0; i < length;i ){ if(hashMap.containsKey(nums[i])){ //如果已经包含，次数加一 hashMap.put(nums[i], hashMap.get(nums[i]) 1); } else { hashMap.put(nums[i], 1); } } // 遍历hashMap for (Integer integer : hashMap.keySet()) { if(hashMap.get(integer) > length/2){ target = integer; break; } } return target; }

分析：算法的时间复杂度是O(n),但是用到了HashMap空间复杂度是O(N)；

2.3 第三个思路：能否一次遍历就把目标值取出，并且不使用额外的空间？

目标值的出现总次数，减去其他值的出现总次数，结果仍是大于等于1的，有一点动态规划的思想在

public int majorityElement(int[] nums) { int num = 1; int target = nums[0]; for(int i = 1; i<nums.length;i ){ if(nums[i]==target){ num ; } else{ num--; } if(num==0){ target = nums[i]; num = 1; } } return target; }

分析：算法的时间复杂度是O(n),空间复杂度是常量O(1)；

,