精华内容
下载资源
问答
  • leetcode求众数

    2021-09-20 23:31:51
    = 1 if dict_num[item] > len(nums) // 2: return item return -1 摩尔投票法,两个不同的数相互抵消,剩下的区间中众数仍然是众数 class Solution: def majorityElement(self, nums: List[int]) -> int: # 时间...

    在这里插入图片描述

    1. 哈希法
    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            # 时间复杂度o(n)
            # 空间复杂度O(n)
    
            dict_num = {}
            for item in nums:
                if item in dict_num:
                    dict_num[item] +=1
                else:
                    dict_num[item] = 1
    
                if dict_num[item] > len(nums) // 2:
                    return item
    
            return -1
    
    1. 摩尔投票法,两个不同的数相互抵消,剩下的区间中众数仍然是众数
    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            # 时间复杂度o(n)
            # 空间复杂度O(1)
    
            n = len(nums)
            if n <= 0:
                return
    
            res = 0
            count = 0
            for i in range(n):
                if count == 0:
                    res = nums[i]
                    count = 1
                elif nums[i] == res:
                    count += 1
                else:
                    count -=1
            return res
    

    在这里插入图片描述

    1. 哈希表,直接统计频次,返回个数大于1/3的,时间复杂度O(n),空间复杂度O(n)
    class Solution:
        def majorityElement(self, nums: List[int]) -> List[int]:
            # 和递归回溯有啥关系呢
            
            n = len(nums)
            if n <= 0:
                return 
            
            dict_num = {}
            res = set()
            for item in nums:
                if item in dict_num:
                    dict_num[item] +=1
                else:
                    dict_num[item] = 1
                
                if dict_num[item] > n // 3:
                    res.add(item)
            return list(res)
    
    1. 摩尔投票法,使用三个不同元素抵消的策略
    class Solution:
        def majorityElement(self, nums: List[int]) -> List[int]:
            # 个数大于1/2,最多只可能有一个
            # 个数大于1/3,最多只可能有两个
            # 时间复杂度O(n),空间复杂度O(1)
    
            if len(nums) == 0:
                return nums
            
           if len(nums) <= 0:
                return nums
    
            num1 = 0
            num2 = 0
            count1 = 0
            count2 = 0
    
            for item in nums:
                if num1 == item:
                    count1 += 1
                elif num2 == item:
                    count2 += 1
                elif count1 == 0:
                    num1 = item
                    count1 = 1
                elif count2 == 0:
                    num2 = item
                    count2 = 1
                else:
                    count1 -= 1
                    count2 -= 1
            # 验证阶段,返回结果
            res = set()
            count1 = 0
            count2 = 0
            for item in nums:
                if num1 == item:
                    count1 += 1
                elif num2 == item:
                    count2 += 1
    
            if count1 > len(nums) // 3: res.add(num1)
            if count2 > len(nums) // 3: res.add(num2)
    
            return list(res)
    
    展开全文
  • Leetcode 求众数

    2019-04-16 06:46:10
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,2,1,1,1,...

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    你可以假设数组是非空的,并且给定的数组总是存在众数。

    示例 1:

    输入: [3,2,3]
    输出: 3

    示例 2:

    输入: [2,2,1,1,1,2,2]
    输出: 2
    

     

    O(n2),先排序,再比较.

    int cmpfunc(const void * a, const void * b) {
        return *(int *)a - *(int *)b;
    }
    
    int majorityElement(int *nums, int numsSize) {
    
        int i;
        short count;
        int ret;
        qsort(nums,numsSize,sizeof(int),cmpfunc);
    
        count = 1;
        ret = nums[0];
    
        for(i = 1; i < numsSize; i++)
            if(ret == nums[i]) {
                count++;
            } else if(count > numsSize/2) {
                return ret;
            } else {
                count = 1;
                ret = nums[i];
            }
    
        return ret;
    }
    
    

     

    法2

    int cmpfunc(const void * a, const void * b) {
        return *(int *)a - *(int *)b;
    }
     
    int majorityElement(int *nums, int numsSize) {
     
        qsort(nums,numsSize,sizeof(int),cmpfunc);
        return nums[numsSize/2];
    }

     

    法3
    因为题意假设这个数一定存在,所以这个数出现的次数大于其他所有数的和。

    int majorityElement(int *nums, int numsSize) {
    
        int i;
        short count = 1;
        int ret=nums[0];
        
        for(i=1;i<numsSize;i++) 
            if(ret == nums[i]) {
                count++;
            } else {
                count--;
                if(count == 0) {
                    ret = nums[i];
                    count = 1;
                }
            }
            
        return ret;
    }
    

     

    展开全文
  • leetcode 求众数

    2019-03-18 17:35:11
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,2,1,1,1,...

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    你可以假设数组是非空的,并且给定的数组总是存在众数。

    示例 1:

    输入: [3,2,3]
    输出: 3

    示例 2:

    输入: [2,2,1,1,1,2,2]
    输出: 2
    

    解题思路一:

    见到该题的第一反应是先遍历一遍,看每个元素出现的次数,利用hashMap存<元素,次数>。再遍历这个hashMap, 取出来这里面value最大的key,即是所求的众数。

    这样该题的难点就是如何存入和读取hashMap了,而且,假设数组中没有众数,该方法也能去除最多次的那个。

    class Solution{
    public  int majorityElement(int[] nums) {
    	Map map = new HashMap<Integer,Integer>();
    	int count = 0;
    	int res = 0;
    	for (int i =0;i< nums.length;i++) {
    		int temp = 0;
    		if(map.containsKey(nums[i])) {
    			temp = (int) map.get(nums[i]);		
    		}
    		map.put(nums[i], temp+1);
    	}
    	Iterator i = map.entrySet().iterator();
    	while (i.hasNext()) {
    		Map.Entry entry = (Map.Entry) i.next();
    		System.out.println(entry+"--------"+ entry.getKey());
    		if(((int)entry.getValue())>count) {
    			count = (int) entry.getValue();
    			res = (int) entry.getKey();
    		}
    	}
    	return res;
      }
    }

    解题思路二:

    利用众数的定义特点,众数出现的次数大于n/2, 所以用众数和其他的元素次数相互抵消,那众数的次数依然会大于0,这就是众数的特点。

    class Solution {
        public int majorityElement(int[] nums) {
       
    		int count=1;//第一个元素,出现了1次
    		int res = nums[0];
    		for (int i = 1;i<nums.length;i++) {
    			//System.out.println(res+"---------"+nums[i]);
    
    			if(res == nums[i]) {
    				count++;
    			}else {
    				count--;
    				if(count==0) {
    					res = nums[i+1];
    				}
    			}
    		}
    		
    		return res;
    	  
        }
    }

     

    展开全文
  • LeetCode 求众数

    2019-10-08 10:37:28
    题目链接:https://leetcode-cn.com/problems/majority-element/ 题目大意:  略。 分析:  略. 代码如下: 1 class Solution { 2 public: 3 int majorityElement(vector<int>& nums) { ...

    题目链接:https://leetcode-cn.com/problems/majority-element/

    题目大意:

      略。

    分析:

       略.

    代码如下:

     1 class Solution {
     2 public:
     3     int majorityElement(vector<int>& nums) {
     4         int ans = nums[0];
     5         int cnt = 1;
     6         
     7         for(int i = 1; i < nums.size(); ++i) {
     8             if(ans == nums[i]) ++cnt;
     9             else { // 两个两个消,最后剩下来的就是众数
    10                 if(--cnt < 0) {
    11                     ans = nums[i];
    12                     cnt = 1;
    13                 }
    14             }
    15         }
    16         
    17         return ans;
    18     }
    19 };
    View Code

     

    转载于:https://www.cnblogs.com/zaq19970105/p/11475451.html

    展开全文
  • LeetCode 求众数II

    2019-03-03 08:43:57
    给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O...此题与上一题 LeetCode 求众数 就是这题众数的定义是出现超过 ⌊ n/3 ⌋ 次的。并且要求空间复杂度为O(1),...
  • leetcode 求众数II

    2021-10-22 12:28:42
    题目链接 ...找出所有出现超过n/3次的元素,那么在这个数组中,最多只会有2个元素出现的次数超过n/3。这个要是想不通的话,可以假设有3个元素出现的次数都超过了n/3次,那么总的元素就超过n个了,显然不成立。...
  • leetcode求众数c++

    2019-04-29 13:06:51
    求众数 给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1...
  • LeetCode 求众数 C语言

    2019-07-22 11:54:17
    方法二:LeetCode官方题解中的投票算法,感觉思路真的很棒,首先假设第一个数为众数记为suf,遍历数组,若与suf相等的数则count+1,若不相等则-1,当count==0时,将suf改为此时的元素值,这样去掉了相等数量的两个...
  • LeetCode求众数C++版

    2019-05-26 22:12:14
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,...
  • LeetCode 求众数 II

    2019-10-08 10:37:26
    题目链接:https://leetcode-cn.com/problems/majority-element-ii/ 题目大意:  略。 分析:  k个一起删, 最后check一下即可. 代码如下: 1 #define foreach(i,c) for (__typeof(c.begin()) i = c....
  • leetcode 求众数 II

    2019-02-06 23:27:17
    给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。 示例 1: 输入: [3,2,3] 输出: [3] 示例 2: ... majorityElement(...
  • LeetCode 求众数 C++

    2019-01-04 21:35:16
    利用关联容器map,&lt;key,value&gt;中令数组中的数字为key,数字出现的次数为...最后遍历map,将value值大于众数的数据输出 代码如下: class Solution { public: int majorityElement(vector&lt...
  • 【Java】Leetcode求众数

    2019-09-03 11:11:55
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,...
  • LeetCode 求众数 (C++)

    2019-04-02 15:50:02
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,973
精华内容 1,189
热门标签
关键字:

leetcode求众数