169-求众数
题目描述示例思路代码改良后的思路方法一方法二
题目描述
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在众数。
示例
输入: [2,2,1,1,1,2,2] 输出: 2
思路
我最初的思路是将元素作为Key，出现的次数作为Value，用一个HashMap存储，然后获得与Value最大值对应的Key即可
缺点： 使用HashMap占用比较多的内存空间，并且在后边的取值中需要遍历；无论是空间还是时间都不优异
代码
public class _2_Majority {
public static void main(String
[] args
) {
int[] nums
= {2,2,1,1,1,2,2};
_2_Majority majority
= new _2_Majority();
int result
= majority
.majorityElement(nums
);
System
.out
.println("result: " + result
);
}
public int majorityElement(int[] nums
) {
HashMap
<Integer, Integer> hashMap
= new HashMap<>();
for (int i
= 0; i
< nums
.length
; i
++) {
int key
= nums
[i
];
if (hashMap
.containsKey(key
)) {
int value
= hashMap
.get(nums
[i
]);
value
++;
hashMap
.replace(key
, value
);
} else {
hashMap
.put(key
, 1);
}
}
Set
<Integer> keySet
= hashMap
.keySet();
Iterator
<Integer> interator
= keySet
.iterator();
int maxKey
= interator
.next();
while (interator
.hasNext()) {
int key
= interator
.next();
if (hashMap
.get(key
) > hashMap
.get(maxKey
)) {
maxKey
= key
;
}
}
return maxKey
;
}
}
改良后的思路
方法一
由于题目已经说明 众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素 所以排序之后数组中间的数字一定是所求的众数
public int majorityElement(int[] nums
) {
Arrays
.sort(nums
);
return nums
[nums
.length
/2];
}
方法二
public int majorityElement(int[] nums
) {
int cand
= 0;
int times
= 0;
for (int i
= 0; i
< nums
.length
; i
++) {
if (times
== 0) {
cand
= nums
[i
];
times
++;
} else if (cand
== nums
[i
]) {
times
++;
} else if (cand
!= nums
[i
]) {
times
--;
}
}
return cand
;
}
