Massive Algorithms: LeetCode 1150 - Check If a Number Is Majority Element in a Sorted Array

LeetCode 1150 - Check If a Number Is Majority Element in a Sorted Array

https://www.codetd.com/en/article/7011577

It is given by a non-decreasing arrays arranged in sequence nums, and a target value target.
If the value of the array nums in most elements are equal to the target, it returns True, otherwise it returns False.

The so-called majority, refers to an array of length N, it appears to be more than N/2twice.

Example 1:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
interpretation:
number 5 occurred five times, the length of the array of 9.
So, the vast majority of the 5 array, because five times> 9/2.
Example 2:

Input: nums = [10,100,101,101], target = 101
Output: false
interpretation:
number 101 appears twice, the length of the array is 4.
So, instead of an array of 101 elements of the majority, because 2 = 4/2.
prompt:

1 <= nums.length <= 1000
1 <= nums[i] <= 10^9
1 <= target <= 10^9

Thinking

Moderation !!! moderation !!! attention moderation !!!

According 已知条件to achieve题目要求

known conditions

Non-decreasing order of the array are arranged
The majority of meaning
Target value

Subject of the request
target value appears in the array of frequency whether the majority?

Code

Violence to strike the number of occurrences of each unique element

class Solution {
    /**
     * 审题不清楚 求数组中出现频次最多的元素 -是否占绝大多数 -是否为目标数值
     * 应该是    求数组中目标数值的出现次数 -是否大于N/2
     * */
    public boolean isMajorityElement(int[] nums, int target) {
        if (nums.length == 0 | null == nums) return false;
        if (nums.length == 1) return nums[0] == target;
        
        // 通过set的特性获取数组中不重复元素
        HashSet<Integer> set = new HashSet<>();
        for (int i : nums) set.add(i);
        
        // counts 每个不重复元素在数组中的出现频次
        int[] counts = new int[set.size()];
        // numSet 数组中不重复元素
        int[] numSet = new int[set.size()];
        // 遍历counts/numSet的指针
        int index = 0;
        // 遍历set集合
        for (Integer inum : set) {
            int count = 0;
            // 获取元素在数组中出现频次
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == inum) count++;
            }
            counts[index] = count;
            numSet[index] = inum;
            index++;
        }
        
        int half = nums.length / 2;
        // 找出数组中出现频次大于N/2 并且等目标数值的数据
        for (int i = 0; i < set.size(); i++) {
            if (counts[i] > half) return numSet[i] == target;
        }
        
        return false;
    }
}

Traversing the screening data are consistent with the meaning of the questions

class Solution {
    /**
     * 符合题意的答案 求数组中目标数值的出现次数 -是否大于N/2
     * */
    public boolean isMajorityElement(int[] nums, int target) {
        if (nums.length == 0 | null == nums) return false;
        if (nums.length == 1) return nums[0] == target;
        
        // 求目标数值在数组中出现次数
        int count = 0;
        for (int i : nums) if (i == target) count++;
        
        // 出现频次是否大于N/2
        return count*2 > nums.length;
    }
}

Binary search data in line with the meaning of the questions

class Solution {
    /**
     * 符合题意的答案 求数组中目标数值的出现次数 -是否大于N/2
     * 并且用到了题目提供的条件 非递减 顺序排列的数组
     * 可以使用二分查找的方法
     * */
    public boolean isMajorityElement(int[] nums, int target) {
        if (nums.length == 0 | null == nums) return false;
        if (nums.length == 1) return nums[0] == target;
        
        // 通过找到目标数值在数组中的位置index
        int count = 1, index = bs(nums, target);
        if (index < 0) return false;
        
        // 基于index 双向查找等于目标数值的元素
        int i = index-1, j = index+1;
        // --> 0 出现小于target的就中止
        while (i >= 0 && nums[i--] >= target)  count++;
        // --> N 出现大于target的就中止
        while (j < nums.length && nums[j++] <= target)  count++;
        
        return count*2 > nums.length;
    }
    
    /**
     * 二分查找(迭代)
     * */
    int bs(int[] nums, int target) {
        int begin = 0;
        int end = nums.length - 1;

        while(begin <= end) {
            int mid = begin + (end - begin)/2;
            if (target == nums[mid]) return mid;
            else if (target < nums[mid]) end = mid-1;
            else if (target > nums[mid]) begin = mid+1;
        }

        return -(begin+1);
     }
}

https://www.cnblogs.com/slowbirdoflsh/p/11343877.html

给出一个按 非递减 顺序排列的数组 nums，和一个目标数值 target。
假如数组 nums 中绝大多数元素的数值都等于 target，则返回 True，否则请返回 False。

所谓占绝大多数，是指在长度为 N 的数组中出现必须超过 N/2 次。

根据已知条件来达到题目要求

已知条件

非递减 顺序排列的数组
占绝大多数的含义
目标数值

题目要求
目标数值在数组中的出现频次是否占绝大多数?

代码实现

暴力求取每个不重复元素的出现次数

class Solution {
    /**
     * 审题不清楚 求数组中出现频次最多的元素 -是否占绝大多数 -是否为目标数值
     * 应该是    求数组中目标数值的出现次数 -是否大于N/2
     * */
    public boolean isMajorityElement(int[] nums, int target) {
        if (nums.length == 0 | null == nums) return false;
        if (nums.length == 1) return nums[0] == target;
        
        // 通过set的特性获取数组中不重复元素
        HashSet<Integer> set = new HashSet<>();
        for (int i : nums) set.add(i);
        
        // counts 每个不重复元素在数组中的出现频次
        int[] counts = new int[set.size()];
        // numSet 数组中不重复元素
        int[] numSet = new int[set.size()];
        // 遍历counts/numSet的指针
        int index = 0;
        // 遍历set集合
        for (Integer inum : set) {
            int count = 0;
            // 获取元素在数组中出现频次
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == inum) count++;
            }
            counts[index] = count;
            numSet[index] = inum;
            index++;
        }
        
        int half = nums.length / 2;
        // 找出数组中出现频次大于N/2 并且等目标数值的数据
        for (int i = 0; i < set.size(); i++) {
            if (counts[i] > half) return numSet[i] == target;
        }
        
        return false;
    }
}

遍历筛选符合题意的数据

class Solution {
    /**
     * 符合题意的答案 求数组中目标数值的出现次数 -是否大于N/2
     * */
    public boolean isMajorityElement(int[] nums, int target) {
        if (nums.length == 0 | null == nums) return false;
        if (nums.length == 1) return nums[0] == target;
        
        // 求目标数值在数组中出现次数
        int count = 0;
        for (int i : nums) if (i == target) count++;
        
        // 出现频次是否大于N/2
        return count*2 > nums.length;
    }
}

二分查找符合题意的数据

class Solution {
    /**
     * 符合题意的答案 求数组中目标数值的出现次数 -是否大于N/2
     * 并且用到了题目提供的条件 非递减 顺序排列的数组
     * 可以使用二分查找的方法
     * */
    public boolean isMajorityElement(int[] nums, int target) {
        if (nums.length == 0 | null == nums) return false;
        if (nums.length == 1) return nums[0] == target;
        
        // 通过找到目标数值在数组中的位置index
        int count = 1, index = bs(nums, target);
        if (index < 0) return false;
        
        // 基于index 双向查找等于目标数值的元素
        int i = index-1, j = index+1;
        // --> 0 出现小于target的就中止
        while (i >= 0 && nums[i--] >= target)  count++;
        // --> N 出现大于target的就中止
        while (j < nums.length && nums[j++] <= target)  count++;
        
        return count*2 > nums.length;
    }
    
    /**
     * 二分查找(迭代)
     * */
    int bs(int[] nums, int target) {
        int begin = 0;
        int end = nums.length - 1;

        while(begin <= end) {
            int mid = begin + (end - begin)/2;
            if (target == nums[mid]) return mid;
            else if (target < nums[mid]) end = mid-1;
            else if (target > nums[mid]) begin = mid+1;
        }

        return -(begin+1);
     }
}