如何跟客户销售做网站,为网站添加统计,设计师常用的图片网站,东莞营业厅文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 解法三思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;多数元素
出处#xff1a;169. 多数元素
难度
2 级
题目描述
要求
给定… 文章目录 题目标题和出处难度题目描述要求示例数据范围进阶 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 解法三思路和算法代码复杂度分析 题目
标题和出处
标题多数元素
出处169. 多数元素
难度
2 级
题目描述
要求
给定大小为 n \texttt{n} n 的数组 nums \texttt{nums} nums返回其中的多数元素。
多数元素是指在数组中出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{\texttt{n}}{\texttt{2}} \Big\rfloor ⌊2n⌋ 的元素。可以假设数组是非空的并且给定的数组总是存在多数元素。
示例
示例 1
输入 nums [3,2,3] \texttt{nums [3,2,3]} nums [3,2,3] 输出 3 \texttt{3} 3
示例 2
输入 nums [2,2,1,1,1,2,2] \texttt{nums [2,2,1,1,1,2,2]} nums [2,2,1,1,1,2,2] 输出 2 \texttt{2} 2
数据范围 n nums.length \texttt{n} \texttt{nums.length} nnums.length 1 ≤ n ≤ 5 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{5} \times \texttt{10}^\texttt{4} 1≤n≤5×104 -10 9 ≤ nums[i] ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{nums[i]} \le \texttt{10}^\texttt{9} -109≤nums[i]≤109
进阶
你可以使用线性时间复杂度和 O(1) \texttt{O(1)} O(1) 空间复杂度解决此问题吗
解法一
思路和算法
最直观的解法是统计数组中每个元素的出现次数然后寻找出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 的元素。
遍历数组使用哈希表记录每个元素的出现次数遍历结束之后即可得到数组中每个元素的出现次数。然后遍历哈希表对于哈希表中的每个元素得到出现次数返回出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 的元素。
代码
class Solution {public int majorityElement(int[] nums) {MapInteger, Integer counts new HashMapInteger, Integer();for (int num : nums) {counts.put(num, counts.getOrDefault(num, 0) 1);}int majority 0;int n nums.length;SetInteger set counts.keySet();for (int num : set) {if (counts.get(num) n / 2) {majority num;break;}}return majority;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 nums \textit{nums} nums 的长度。遍历数组统计每个元素的出现次数需要 O ( n ) O(n) O(n) 的时间遍历哈希表得到多数元素也需要 O ( n ) O(n) O(n) 的时间。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 nums \textit{nums} nums 的长度。需要创建哈希表记录每个元素的出现次数哈希表中的元素个数不超过 n n n。
解法二
思路和算法
另一个解法是将数组排序后得到多数元素。排序后的数组满足相等的元素一定出现在数组中的相邻位置由于多数元素在数组中的出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋因此排序后的数组中存在至少 ⌊ n 2 ⌋ 1 \Big\lfloor \dfrac{n}{2} \Big\rfloor 1 ⌊2n⌋1 个连续的元素都是多数元素下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 的元素一定是多数元素。理由如下 如果多数元素是数组中的最小元素则排序后的数组从下标 0 0 0 到下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 的元素都是多数元素 如果多数元素是数组中的最大元素则排序后的数组从下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 到下标 n − 1 n - 1 n−1 的元素都是多数元素 如果多数元素不是数组中的最小元素和最大元素则排序后的数组的下标 0 0 0 和下标 n − 1 n - 1 n−1 的元素都不是多数元素多数元素的开始下标一定小于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋结束下标一定大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 的元素一定是多数元素。
因此将数组排序之后返回下标 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 的元素即可。
代码
class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);int n nums.length;return nums[n / 2];}
}复杂度分析 时间复杂度 O ( n log n ) O(n \log n) O(nlogn)其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( n log n ) O(n \log n) O(nlogn) 的时间。 空间复杂度 O ( log n ) O(\log n) O(logn)其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( log n ) O(\log n) O(logn) 的递归调用栈空间。
解法三
思路和算法
寻找多数元素的另一种解法是摩尔投票算法其时间复杂度是 O ( n ) O(n) O(n)空间复杂度是 O ( 1 ) O(1) O(1)。
摩尔投票算法由 Robert S. Boyer 和 J Strother Moore 提出该算法的基本思想是在每一轮投票过程中从数组中删除两个不同的元素直到投票过程无法继续此时数组为空或者数组中剩下的元素都相等。
摩尔投票算法的具体做法如下。 维护多数元素 majority \textit{majority} majority 和多数元素的出现次数 count \textit{count} count初始时 majority \textit{majority} majority 为数组的首个元素 count 1 \textit{count} 1 count1。 遍历数组中除了首个元素以外的所有元素当遍历到元素 num \textit{num} num 时执行如下操作。 如果 count 0 \textit{count} 0 count0则将 majority \textit{majority} majority 的值更新为 num \textit{num} num否则不更新 majority \textit{majority} majority 的值。 如果 num majority \textit{num} \textit{majority} nummajority则将 count \textit{count} count 加 1 1 1否则将 count \textit{count} count 减 1 1 1。
由于这道题中多数元素总是存在因此遍历结束之后 majority \textit{majority} majority 即为多数元素。
如果不保证多数元素一定存在则当多数元素不存在时遍历结束之后的 majority \textit{majority} majority 可能为数组中的任意一个元素。此时需要再次遍历数组统计 majority \textit{majority} majority 在数组中的出现次数当 majority \textit{majority} majority 的出现次数大于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 时 majority \textit{majority} majority 是多数元素当 majority \textit{majority} majority 的出现次数小于等于 ⌊ n 2 ⌋ \Big\lfloor \dfrac{n}{2} \Big\rfloor ⌊2n⌋ 时没有多数元素。
考虑示例 1 nums [ 3 , 2 , 3 ] \textit{nums} [3, 2, 3] nums[3,2,3]使用摩尔投票算法寻找多数元素的过程如下。 初始化 majority nums [ 0 ] 3 \textit{majority} \textit{nums}[0] 3 majoritynums[0]3 count 1 \textit{count} 1 count1。 遍历到 nums [ 1 ] 2 \textit{nums}[1] 2 nums[1]2。 由于 count 1 \textit{count} 1 count1因此不更新 majority \textit{majority} majority 的值。 由于当前元素不等于 majority \textit{majority} majority因此将 count \textit{count} count 减 1 1 1 count \textit{count} count 变成 0 0 0。 遍历到 nums [ 2 ] 3 \textit{nums}[2] 3 nums[2]3。 由于 count 0 \textit{count} 0 count0因此将 majority \textit{majority} majority 的值更新为当前元素 3 3 3。 由于当前元素等于 majority \textit{majority} majority因此将 count \textit{count} count 加 1 1 1 count \textit{count} count 变成 1 1 1。 遍历结束 majority 3 \textit{majority} 3 majority3多数元素是 3 3 3。
代码
class Solution {public int majorityElement(int[] nums) {int majority nums[0];int count 1;int n nums.length;for (int i 1; i n; i) {int num nums[i];if (count 0) {majority num;}if (num majority) {count;} else {count--;}}return majority;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组 nums \textit{nums} nums 一次。 空间复杂度 O ( 1 ) O(1) O(1)。
