剑指 Offer 39. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size(), ans = nums[rand() % n];
while(true){
int cnt = 0;
for(int i = 0; i < n; ++ i){
if(nums[i] == ans)cnt ++;
}
if(cnt > n / 2)return ans;
ans = nums[rand() % n];
}
return 0;
}
};
算法思路
这题有两种解法，第一种是用map来存储每个数字出现的次数，但map的存取时间和空间要求就比较大。第二种方法是随机算法(拉斯维加斯算法)，随机抽取一个数，然后判断该数是不是结果，如果是结果直接返回，不是结果的话继续抽随机数。
剑指 Offer 66. 构建乘积数组
给定一个数组 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]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
提示：
- 所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
int n = a.size();
if(n == 1)return a;
vector<vector<int>> dp(2, vector<int>(n));
for(int i = 0; i < n; ++ i){
if(i == 0){
dp[0][i] = a[i];
dp[1][n - 1- i] = a[n - 1 - i];
}else{
dp[0][i] = dp[0][i - 1] * a[i];
dp[1][n - 1 - i] = dp[1][n - i] * a[n - i - 1];
}
}
vector<int> ans(n);
for(int i = 0; i < n; ++ i){
if(i == 0){
ans[i] = dp[1][i + 1];
}else if(i == n - 1){
ans[i] = dp[0][i - 1];
}else{
ans[i] = dp[0][i - 1] * dp[1][i + 1];
}
}
return ans;
}
};
算法思路
这一题求出本身外其它元素的乘积，我们可以求它前半部分的积和后半部分的积，然后就可以得出结果，这里用的是类似前缀和的算法(前缀积, doge)，我们可以从头到尾求到某个位置前所有元素的乘积和从尾到头求到某个位置所有元素的乘积，这样我们在求某一个位置的结果时只需要求其前缀积和后缀积的乘积就是结果。
【剑指Offer】系列：
【剑指Offer】栈
【剑指Offer】链表
【剑指Offer】字符串
【剑指Offer】查找算法
【剑指Offer】查找算法(1)
【剑指Offer】搜索与回溯算法
【剑指Offer】搜索与回溯算法(1)
【剑指Offer】动态规划
【剑指Offer】动态规划(1)
【剑指Offer】动态规划(2)
【剑指Offer】双指针
【剑指Offer】双指针(1)
【剑指Offer】双指针(2)
【剑指Offer】搜索与回溯算法(2)
【剑指Offer】搜素与回溯算法(3)
【剑指Offer】排序
【剑指Offer】排序(1)
【剑指Offer】搜索与回溯算法(4)
【剑指Offer】搜索与回溯算法(5)
【剑指Offer】分治算法
【剑指Offer】位运算
【剑指Offer】位运算(1)