Leetcode sword finger offer brush questions - day 23

Leetcode The finger of the sword Offer How to brush questions ：

Leetcode The finger of the sword Offer Brush problem - Learning plan directory _DEGv587 The blog of -CSDN Blog

The finger of the sword Offer 39. A number that appears more than half the times in an array

Solution 1 ： Sort library function + Median

class Solution {
    public int majorityElement(int[] nums) {
        if (nums.length == 0) return -1;
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

Solution 2 ：hashmap

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
            if (map.get(n) > (nums.length / 2)) {
                return n;
            }
        }
        return -1;
    }
}

Solution 3 ： Moore voting , Limit for limit , Left to the end is more than half

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0, ret = 0;
        for (int n : nums) {
            if (count == 0) {
                ret = n;
                ++count;
            } else {
                count = ret == n ? ++count : --count;
            }
        }

        return ret;
    }
}

The finger of the sword Offer 66. Building a product array

solution ： From left to right , Then multiply from right to left

class Solution {
    public int[] constructArr(int[] a) {
        int len = a.length;
        int[] ret = new int[len];
        // From left to right 
        int cur = 1;
        for (int i = 0; i < len; ++i) {
            ret[i] = cur;
            cur *= a[i];
        }
        // From right to left 
        cur = 1;
        for (int i = len - 1; i >= 0; --i) {
            ret[i] *= cur;
            cur *= a[i];
        }

        return ret;
    }
}