Day23_数组计算_剑指Offer

IT蛋

2023-04-14 12:41

阅读2451

IT蛋

2023-04-14 12:41

阅读 2451

数组中出现次数超过一半的数字

Easy 原题连接：数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

输出: 2

限制：

1 <= 数组长度 <= 50000

解题思路

摩尔投票：记录一个值当作目标值，对比接下来的值是否和目标值一致，一致则计数加一，否则减一，当计数为零时更换目标值

使用前提：数组中一定存在超过一半的符合要求的数，否则算法不成立【1，1，4，4，4，7，7】会返回 7 而不是 4 ，当数组中一定存在超过一半的目标数，剩余的数全部对撞目标数，留下的也一定是目标数。

Java代码

class Solution {

public int majorityElement(int[] nums) {

//摩尔投票算法：对拼消耗

int ans = 0, maxNum = 0;

for(int num : nums) {

if(maxNum == 0) {

ans = num;

}

if(num == ans) {

maxNum++;

}else {

maxNum--;

}

return ans;

}

构建乘积数组

medium 原题连接：构建乘积数组

给定一个数组 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

解题思路

题目提示长度可能达到10w，循环暴力破解肯定是超时下策，但是每个数乘积又需要遍历得到，这时应该考虑复用计算结果

将计算 i 位的目标乘积分为两部分来看的话：i 以前的累乘 * i 以后的累乘

计算 i 位的前 i-1 位目标乘积时，i+1 位只需要在此基础上多乘个 a[i]

计算 i 位的后 a.length - i 位乘积时，i-1 位只需要再次基础上多乘个 a[i]

实现：

创建对应长度的数组，附上1便于做乘积
首次循环，计算 i 之前的累积，使用中间值mid存储累积结果
第二次循环，计算 i 之后的累积，使用中间值mid存储累积结果
返回结果

Java代码

class Solution {

public int[] constructArr(int[] a) {

int[] ans = new int[a.length];

int mid = 1;

for(int i=0; i<ans.length; i++) {

ans[i] = 1;

ans[i] *= mid;

mid *= a[i];

}

mid = 1;

for(int i=ans.length-1; i>=0; i--) {

ans[i] *= mid;

mid *= a[i];

}

return ans;

}

笔试笔试，面试面试。应该签三方吗？

我的博客：Day23_数组计算_剑指Offer | IT蛋的个人博客 (xcscx.github.io )