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

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

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

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

示例：

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

限制：

  1. 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]

提示：

  1. 所有元素乘积之和不会溢出 32 位整数
  2. a.length <= 100000

解题思路

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

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

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

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

实现：

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

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;
    }
}