169.Majority Element

た入场券 2022-06-10 14:12 92阅读 0赞

/\*  
题目要求：  
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.  
  
You may assume that the array is non-empty and the majority element always exist in the array.  
主元素问题  
给定一串数字，从中找出超过n/2的数，这个数字定义为主元素  
最开始的时候用了两个for循环计算出来，但是时间复杂度太大了，达到了n的平方，在提交的时候，时间受限。  
后来发现这个题目的多种解法，时间复杂度都小的多  
1.两个for循环解决  
2.首先进行快速排序或者堆排序，然后直接输出第n/2的元素，必定是主元素  
3.主元素算法，先设定一个比较值count=0，然后向后一个数比较，如果相同，则count++；若不同，count--。若相邻两个数都不一样，则count=-1，  
这时候将这两个元素删除掉，那么对于剩下的数来说，主元素还是主元素，并不会发生改变。  
这是算法的核心思想，这样的话算法的时间复杂度最大才是O（n）  
\*/  
int majorityElement(int\* nums, int numsSize)  
\{  
    int i,count = 0;  
    int mainer = nums\[0\];  
    for(i=1;i<numsSize;i++)  
    \{  
        if(mainer!=nums\[i\])  
            count--;  
        else  
            count++;  
        if(count==-1)  
        \{  
            mainer = nums\[i+1\];  
            i++;  
            count = 0;  
        \}  
    \}  
    if(count>0)  
        return mainer;  
    return;  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Easy - 169. Majority Element

Topic Array Divide and Conquer Bit Manipulation Description [https://lee

桃扇骨/ 2022年12月29日 09:53/ 0 赞/ 87 阅读

相关 169. Majority Element （寻找多数元素）

Given an array of size n, find the majority element. The majority element is the element

你的名字/ 2022年07月15日 01:20/ 0 赞/ 147 阅读

相关 [leetcode]: 169. Majority Element

1.题目描述 Given an array of size n, find the majority element. The majority element is t

Love The Way You Lie/ 2022年06月16日 03:50/ 0 赞/ 114 阅读

相关 169.Majority Element

/\ 题目要求： Given an array of size n, find the majority element. The majority element i

た入场券/ 2022年06月10日 14:12/ 0 赞/ 93 阅读

相关 leetcode 169. Majority Element 摩尔投票法

Given an array of size n, find the majority element. The majority element is the element

野性酷女/ 2022年06月08日 07:28/ 0 赞/ 126 阅读

相关 LeetCode169. Majority Element解答

天气冷了，有男朋友的抱男朋友，有女朋友的抱女朋友，而我就比较牛逼了我不冷 \先来看一下题目 > Given an array of size n, find the

比眉伴天荒/ 2022年06月07日 11:26/ 0 赞/ 104 阅读

相关 169.Majority Element

> Given an array of size n, find the majority element. The majority element is the eleme

水深无声/ 2022年05月30日 06:37/ 0 赞/ 122 阅读

相关 LeetCode 169.Majority Element (求众数)

题目描述：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 `⌊ n/2 ⌋` 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

港控/mmm°/ 2022年05月10日 15:00/ 0 赞/ 124 阅读

相关 LeetCode:169. Majority Element(找出大多数元素)

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

亦凉/ 2022年04月12日 08:16/ 0 赞/ 210 阅读

相关 LeetCode : 169. Majority Element 众数

试题 Given an array of size n, find the majority element. The majority element is the el

ゞ浴缸里的玫瑰/ 2021年06月24日 16:11/ 0 赞/ 327 阅读