算法题 |
---|
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3]
输出:3
示例 2:
输入:[2,2,1,1,1,2,2]
输出:2
提示:
众数总比非众数多 因此最终能让票数count保持大于0的数就是众数。
注意:每当count变回0时就更换候选人,继续统计后续票数。
思路解析
代码:
public class Solution {
public int MajorityElement(int[] nums) {
//投票法
int condidate = nums[0];
int count = 1;
for(int j = 1;j<nums.Length;j++)
{
if(count == 0)
{
count = 1;
condidate = nums[j];
continue;
}
if(nums[j] != condidate)
{
count--;
}
else
{
count++;
}
}
return condidate;
}
}
执行结果
通过
执行用时:108 ms,在所有 C# 提交中击败了76.44%的用户
内存消耗:29.8 MB,在所有 C# 提交中击败了27.49%的用户
思路解析
我们知道出现次数最多的元素大于⌊ 2/n⌋ 次,所以可以用哈希表来快速统计每个元素出现的次数。
我们使用哈希映射(HashMap)来存储每个元素以及出现的次数。对于哈希映射中的每个键值对,键表示一个元素,值表示该元素出现的次数。
我们用一个循环遍历数组nums
并将数组中的每个元素加入哈希映射中。在
这之后,我们遍历哈希映射中的所有键值对,返回值最大的键。
我们同样也可以在遍历数组 nums
时候使用打擂台的方法,维护最大的值,这样省去了最后对哈希映射的遍历。
代码:
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
} else {
counts.put(num, counts.get(num) + 1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = countNums(nums);
Map.Entry<Integer, Integer> majorityEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}
return majorityEntry.getKey();
}
}
执行结果
通过
执行用时:13 ms,在所有 Java 提交中击败了21.51%的用户
内存消耗:38.6 MB,在所有 Java 提交中击败了52.15%的用户
复杂度分析
时间复杂度:O( n )
空间复杂度:O( n )
代码:
class Solution {
private int randRange(Random rand, int min, int max) {
return rand.nextInt(max - min) + min;
}
private int countOccurences(int[] nums, int num) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
public int majorityElement(int[] nums) {
Random rand = new Random();
int majorityCount = nums.length / 2;
while (true) {
int candidate = nums[randRange(rand, 0, nums.length)];
if (countOccurences(nums, candidate) > majorityCount) {
return candidate;
}
}
}
}
执行结果
通过
执行用时:1 ms,在所有 Java 提交中击败了99.96%的用户
内存消耗:44.5 MB,在所有 Java 提交中击败了12.18%的用户
C#
和 Java
两种编程语言进行解题