网站海报是怎么做的,肇庆seo排名外包,为什么点不开网站,线上海报设计网站优质博文#xff1a;IT-BLOG-CN 一、题目
给定一个大小为n的数组nums#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1#xff1a; 输入#xff1a;nums [3,2,3… 优质博文IT-BLOG-CN 一、题目
给定一个大小为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】哈希映射HashMap 来存储每个元素以及出现的次数。对于哈希映射中的每个键值对键表示一个元素值表示该元素出现的次数。我们用一个循环遍历数组nums并将数组中的每个元素加入哈希映射中。在这之后我们遍历哈希映射中的所有键值对返回值最大的键。我们同样也可以在遍历数组nums时候使用打擂台的方法维护最大的值这样省去了最后对哈希映射的遍历。
class Solution {public int majorityElement(int[] nums) {// 思想 通过 hashMap 存放 value 和 count , 如果 count n/2 直接返回if (nums.length 0) {return 0;}int mid nums.length/2;MapInteger, Integer map new HashMapInteger, Integer(); for (int i 0; i nums.length; i) {map.put(nums[i], map.getOrDefault(nums[i], 0) 1);if (map.getOrDefault(nums[i], 0) mid) {return nums[i];}}return 0;}
}时间复杂度 O(n)其中n是数组nums的长度。我们遍历数组nums一次对于nums中的每一个元素将其插入哈希表都只需要常数时间。如果在遍历时没有维护最大值在遍历结束后还需要对哈希表进行遍历因为哈希表中占用的空间为O(n)可参考下文的空间复杂度分析那么遍历的时间不会超过O(n)。因此总时间复杂度为O(n)。 空间复杂度 O(n)哈希表最多包含n−⌊n/2⌋个键值对所以占用的空间为O(n)。这是因为任意一个长度为n的数组最多只能包含n个不同的值但题中保证nums一定有一个众数会占用最少⌊n/2⌋1个数字。因此最多有n−(⌊n/2⌋1)个不同的其他数字所以最多有n−⌊n/2⌋个不同的元素。
【2】排序 如果将数组nums中的所有元素按照单调递增或单调递减的顺序排序那么下标为⌊n/2⌋的元素下标从0开始一定是众数。
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return (nums[nums.length/2]);}
}时间复杂度 O(nlogn)将数组排序的时间复杂度为O(nlogn)。 空间复杂度 O(logn)如果使用语言自带的排序算法需要使用O(logn)的栈空间。如果自己编写堆排序则只需要使用O(1)的额外空间。
【3】Boyer-Moore 投票算法 如果我们把众数记为1把其他数记为−1将它们全部加起来显然和大于0从结果本身我们可以看出众数比其他数多。
oyer-Moore算法的本质和分治十分类似。我们首先给出Boyer-Moore算法的详细步骤 【1】我们维护一个候选众数candidate和它出现的次数count。初始时candidate可以为任意值count为0 【1】我们遍历数组nums中的所有元素对于每个元素x在判断x之前如果count的值为0我们先将x的值赋予candidate随后我们判断x如果x与candidate相等那么计数器count的值增加1如果x与candidate不等那么计数器count的值减少1。在遍历完成后candidate即为整个数组的众数。
我们举一个具体的例子例如下面的这个数组
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]在遍历到数组中的第一个元素以及每个在 | 之后的元素时candidate都会因为count的值变为0而发生改变。最后一次candidate的值从5变为7也就是这个数组中的众数。
Boyer-Moore算法的正确性较难证明这里给出一种较为详细的用例子辅助证明的思路供读者参考首先我们根据算法步骤中对count的定义可以发现在对整个数组进行遍历的过程中count的值一定非负。这是因为如果count的值为0那么在这一轮遍历的开始时刻我们会将x的值赋予candidate并在接下来的一步中将count的值增加1。因此count的值在遍历的过程中一直保持非负。
那么count本身除了计数器之外还有什么更深层次的意义呢我们还是以数组
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]作为例子首先写下它在每一步遍历时candidate和count的值
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
candidate: 7 7 7 7 7 7 5 5 5 5 5 5 7 7 7 7
count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4我们再定义一个变量value它和真正的众数maj绑定。在每一步遍历时如果当前的数x和maj相等那么value的值加1否则减1。value的实际意义即为到当前的这一步遍历为止众数出现的次数比非众数多出了多少次。我们将value的值也写在下方
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4有没有发现什么我们将count和value放在一起
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4
value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4发现在每一步遍历中count和value要么相等要么互为相反数并且在候选众数candidate就是maj时它们相等candidate是其它的数时它们互为相反数
为什么会有这么奇妙的性质呢这并不难证明我们将候选众数candidate保持不变的连续的遍历称为「一段」。在同一段中count的值是根据candidate x的判断进行加减的。那么如果candidate恰好为maj那么在这一段中count和value的变化是同步的如果candidate不为maj那么在这一段中count和value的变化是相反的。因此就有了这样一个奇妙的性质。
这样以来由于我们证明了count的值一直为非负在最后一步遍历结束后也是如此由于value的值与真正的众数maj绑定并且它表示「众数出现的次数比非众数多出了多少次」那么在最后一步遍历结束后value的值为正数
在最后一步遍历结束后count非负value为正数所以它们不可能互为相反数只可能相等即count value。因此在最后「一段」中count的value的变化是同步的也就是说candidate中存储的候选众数就是真正的众数maj。
class Solution {public int majorityElement(int[] nums) {int count 0;Integer candidate null;for (int num : nums) {if (count 0) {candidate num;}count (num candidate) ? 1 : -1;}return candidate;}
}时间复杂度 O(n)Boyer-Moore算法只对数组进行了一次遍历。 空间复杂度 O(1)Boyer-Moore算法只需要常数级别的额外空间。
