题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
限制：
- 1 <= 数组长度 <= 50000
哈希这题和 leetcode-229. 求众数 II 一样。
思路：
- 统计每个元素的出现次数，找次数超过 n / 2 n/2 n/2 的元素。
class Solution {
public int majorityElement(int[] nums) {
Map map = new HashMap<>();
// 统计次数
for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
// 找出现次数超过数组长度的一半的数字
for (int i : nums) {
if (map.get(i) > nums.length / 2) {
return i;
}
}
return -1; // 不存在
}
}
以上代码中 2 个 for 可以合成一个 for 循环（但是复杂度并没有本质变化）
class Solution {
public int majorityElement(int[] nums) {
int n = nums.length;
Map map = new HashMap<>();
for (int x : nums) {
map.put(x, map.getOrDefault(x, 0) + 1);
if (map.get(x) > n / 2) return x;
}
return -1;
}
}
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
思路：
- 对所有元素排序；
- 则 n u m s [ n u m s . l e n g t h / 2 ] nums[nums.length / 2] nums[nums.length/2] 即为 出现的次数超过数组长度的一半的元素。
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
- 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度：
O
(
1
)
O(1)
O(1) （忽略快排消耗栈空间
O
(
l
o
g
n
)
O(logn)
O(logn)）
以上 排序、哈希 总和时间和空间上都不是最优的，此类在集合中找 多数元素（众数）的题使用 摩尔投票法 是一种较好的选择…
参考之前的一篇文章 leetcode-229. 求众数 II.
思路：樂
-
投票阶段：不同元素，则“抵消”；相同元素，则累加
-
计数阶段：最终得到的“可能” 候选者 cand，不一定是最终 的众数，所以还需要一轮 计算阶段，来判断后选择 cand 是不是最终的“众数”
比如，[1,2,3] 得到的 cand 为 3，但是其实这个 nums 中并没有 众数。所以，需要 计数阶段
class Solution {
public int majorityElement(int[] nums) {
int cand = -1;
int cnt = 0;
// 1、投票阶段
for (int i : nums) {
if (cnt == 0) {
cand = i;
cnt = 1;
} else {
if (cand != i) { // 不同元素，则“抵消”
cnt--;
} else { // 相同元素，则累加
cnt++;
}
}
}
// 2、计数阶段
cnt = 0;
for (int i : nums) {
if (i == cand) cnt++;
}
if (cnt > nums.length / 2) return cand;
else return -1; // 不存在
}
}
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
题目描述
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
提示：
- 所有元素乘积之和不会溢出 32 位整数
- a.length <= 100000
思路：樂
- 先求下三角矩阵（从前到后）
r e s [ i ] = 1 ∗ a [ 0 ] ∗ . . . ∗ a [ i − 1 ] res[i] = 1 * a[0] * ... * a[i-1] res[i]=1∗a[0]∗...∗a[i−1] - 再求上三角矩阵（从后向前）
r e s [ i ] ∗ = ( a [ n − 1 ] ∗ . . ∗ a [ i + 1 ] res[i] *= (a[n-1]*..*a[i+1] res[i]∗=(a[n−1]∗..∗a[i+1]
class Solution {
public int[] constructArr(int[] a) {
int n = a.length;
int[] res = new int[n];
// 下三角
int p = 1;
for (int i = 0; i < n; i++) {
res[i] = p;
p *= a[i];
}
// 上三角
int q = 1;
for (int i = n - 1; i >= 0; i--) { // 逆序
res[i] *= q;
q *= a[i];
}
return res;
}
}
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
