剑指 Offer 39. 数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。 


输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2
🔗题目链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/


方法一：排序求中位数

超过数组一半的数，那么进行排序之后，必然会出现在中心位置 
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        return length % 2 == 0 ? nums[length / 2 - 1] : nums[length / 2];
    }
}

方法二：哈希法

维护一个哈希表存储对应数字出现的次数，超过数组一半的即为结果，但这种做法时间复杂度较高 
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            int value = map.getOrDefault(num, 0) + 1;
            map.put(num, value);
        }
        int res = 0;
        for(int key : map.keySet()){
            if(map.get(key) > nums.length / 2){
                res = key;
                break;
            }
        }
        return res;
    }
}

方法三：摩尔投票法

其实就是遍历数组，拼消耗，假设当前数为超过一半的数，遇到不同的就-1，相同的就+1，等于0说明当前超过一半的数被消耗完了，设定新的数作为超过一半的数，以此类推，最终剩下的即为结果数
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0; //票数
        int m = 0; //记录超过一半的数
        for(int num : nums){
            if(count == 0){
                //如果票数为0，就假设当前数为超过一半的数
                m = num;
            }
            //等于超过一半的数票数就+1，否则-1，当票数为0时就切换
            count += num == m ? 1 : -1;
        }
        return m;
    }
}

剑指 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]
🔗题目链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof

思路

整体思路，结果集中任何一个元素 = 其左边所有元素的乘积 * 其右边所有元素的乘积。先循环构建左边的乘积保存在数组b中，再循环构建右边的乘积，并在此过程中乘以左边的乘积保存于数组b中，这道题构建图表更容易理解。

代码实现 

class Solution {
    public int[] constructArr(int[] a) {
        int length = a.length;
        if(length == 0){
            return new int[length];
        }
        int[] b = new int[length];
        b[0] = 1;
        //累乘当前元素左边的数，b[i-1]中维护前一个数的累乘结果，只需乘以a[i-1]即可
        for(int i = 1; i < length; i++){
            b[i] = b[i - 1] * a[i - 1];
        }
        //从后往前累乘右边的数存于temp，再与对应的左边相乘
        int temp = 1;
        for(int i = length - 2; i >= 0; i--){
            temp *= a[i + 1];
            b[i] *= temp;
        }
        return b;
    }
}