精华内容
下载资源
问答
  • 众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2 题目解析 题目意思很好理解:给...

    题目描述

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

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

    示例 1:

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

    示例 2:

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

    题目解析

    题目意思很好理解:给你一个数组,里面有一个数字出现的次数超过了一半,你要找到这个数字并返回。

    解法一:暴力解法

    遍历整个数组,同时统计每个数字出现的次数。

    最后将出现次数大于一半的元素返回即可。

    动画描述(来源网络)

    代码实现

    class Solution {
        public int majorityElement(int[] nums) {
            int majorityCount = nums.length/2;
    
            for (int num : nums) {
                int count = 0;
                for (int elem : nums) {
                    if (elem == num) {
                        count += 1;
                    }
                }
                if (count > majorityCount) {
                    return num;
                }
    
            }  
        }
    }
    

    复杂度分析

    时间复杂度:O(n2)

    暴力解法包含两重嵌套的 for 循环,每一层 n 次迭代,因此时间复杂度为 O(n2) 。

    空间复杂度:O(1)

    暴力解法没有分配任何与输入规模成比例的额外的空间,因此空间复杂度为 O(1)。

    解法二:哈希表法

    这个问题可以视为查找问题,对于查找问题往往可以使用时间复杂度为 O(1) 的 哈希表,通过以空间换时间的方式进行优化。

    直接遍历整个 数组 ,将每一个数字(num)与它出现的次数(count)存放在 哈希表 中,同时判断该数字出现次数是否是最大的,动态更新 maxCount,最后输出 maxNum。

    动画描述(来源网络)

    代码实现

    class Solution {
        public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        // maxNum 表示元素,maxCount 表示元素出现的次数
        int maxNum = 0, maxCount = 0;
        for (int num: nums) {
          int count = map.getOrDefault(num, 0) + 1;
          map.put(num, count);
          if (count > maxCount) {
            maxCount = count;
            maxNum = num;
          }
        }
        return maxNum;
      }
    }
    

    复杂度分析

    时间复杂度:O(n)

    总共有一个循环,里面哈希表的插入是常数时间的,因此时间复杂度为 O(n)。

    空间复杂度:O(n)

    哈希表占用了额外的空间 O(n),因此空间复杂度为 O(n)。

    展开全文
  • 众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2 这道题用摩尔投票法,这种方法是...

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

    这道题用摩尔投票法,这种方法是因为题目中说众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。所以设置一个计数器,选定第一个值作为起始值,然后后面的值如果是这个值那么计数加一,如果不等,那么计数减一,当计数器的值为零时,选取当前值作为新值继续计数。因为众数肯定大于1/2所以最后计数器不为零的数肯定是众数。

    Java实现:

    class Solution {
        public int majorityElement(int[] nums) {
            int count = 0;
            int num = nums[0];
            for(int i = 0; i < nums.length; i++){
                if(num == nums[i]){
                    count++;
                }else{
                    count--;
                    if(count == 0){
                        num = nums[i];
                        count++;
                    }
                    
                }
            }
            return num;   
        }
    }
    
    展开全文
  • 众数是指在数组中出现次数大于[n/2] 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入 : [3, 2, 3] 输出 : 3 示例 2 : 输入 : [2, 2, 1, 1, 1, 2, 2] 输出 : 2 思想方法:从第一个数...

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

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

    示例 1:

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

    示例 2 :

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

    思想方法:从第一个数开始count=1,遇到相同的就加1,遇到不同的就减1,减到0就重新换个数开始计数,总能找到最多的那个,如果不太理解,把代码运行下,就能想通。

    #define _CRT_SECURE_NO_WARNINGS 
    #include <stdio.h>
    #include <stdlib.h>
    int majorityElement(int* nums, int numsSize) {
    	int count = 1;
    	int zhong = nums[0];
    	for (int i = 1; i<numsSize; i++)
    	{
    		if (zhong == nums[i])
    		{
    			count++;
    		}
    		else
    		{
    			count--;
    			if (count == 0)
    			{
    				zhong = nums[i + 1];
    			}
    		}
    	}
    	return zhong ;
    }
    int main()
    {
    	int num[] = { 3, 3, 2, 3, 4, 3,2, 2, 3 };
    	int len = sizeof(num) / sizeof(int);
    	int a = majorityElement(num, len);
    	printf("%d\n", a);
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 方法一:取数组第一个元素,去循环重复一个就计数为1,没遇到一样的就减一,直到为零换下一个...

    自己整理的不算转载

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

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

    示例 1:

     

    方法一:取数组第一个元素,去循环重复一个就计数为1,没遇到一样的就减一,直到为零换下一个元素去数组碰,剩下的一定是最多的那个

    class Solution {
      
        public static void main(String[] args) {
            int[] a = {2,2,1,1,1,2,2};
            System.out.println(majorityElement(a));
        }

        public static int majorityElement(int[] nums) {
            int a = nums[0];
            int count = 1;
            for(int num : nums) {
                if(num == a) {
                    count ++;
                }else {
                    count --;
                    if(count == 0) {
                        a = num;
                        count = 1;
                    }
                }
            }
            return a;
        }
    }

     

    方法二:先sort排下序,然后取最中间的那个数因为定义的是个数大于数组长度的二分之一

     

    public static void main(String[] args) {
        int[] a = {2,2,1,1};
        System.out.println(majorityElement(a));
    }
    
    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    展开全文
  • 众数是指在一组数据中,出现次数最多的数。例如:1, 1, 3 中出现次数最多的数为 1,则众数为 1。 给定一组数,你能求出众数吗? Input 输入数据有多组(数据组数不超过 50),到 EOF 结束。 对于每组数据: •...
  • 一个集合如果允许存在相同的元素,则称之为多重集合.... 例如, S = { 1,2,2,2,3,5 } 的众数是 2, 其重数为 3. 本题对于给定的由 n 个自然数组成的多重集 S, 编程计算 S 的众数及其重数. Input
  • 例如:S={1,2,2,2,3,5},则多重集S的众数是2,其重数为3。 对于给定的由m个自然数组成的多重集S,计算出S的众数及其重数。 众数------一组元素中出现的次数是最多的 重数-------这个数出现的总次数 ...
  • 设计思路:给数组排序,由于众数出现次数大于n/2,所以第n/2个元素就是众数。 function mostNum(arr){ var arr2 = arr.sort((a,b)=>{return b-a;}); var zhong = arr[parseInt(arr.length/2)]; return zhong...
  • 众数

    2019-11-27 14:28:03
    众数是指在一组数据中,出现次数最多的数。例如:1, 1, 3 中出现次数最多的数为 1,则众数为 1。 给定一组数,你能求出众数吗? Input 输入数据有多组(数据组数不超过 50),到 EOF 结束。 对于每组数据: •第 1 ...
  • 众数

    2019-08-22 10:21:03
    求众数的方法有很多,这里主要说明的是...众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,2,1,1,1,2,2] ...
  • 寻找众数

    2019-10-07 17:40:48
    众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3]输出: 3示例2: 输入: [2,2,1,1,1,2,2]输出:2 1.很简单的排序,因为众数大于总...
  • 众数问题

    2019-11-22 10:44:55
    众数问题 Time Limit: 2000 ms Memory Limit: 65536 KiB Problem Description ...多重集S的众数是2,其重数为3。对于给定的由n 个自然数组成的多重集S,计算S的众数及其重数。如果出现多个众数,请输出...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,597
精华内容 1,038
关键字:

众数是