寻找主元素

分手后的思念是犯贱 2022-06-13 08:49 196阅读 0赞

描述

设A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称x是A的主元素。现在请你在一个数组中找到主元素。

输入

第一行：n（0 < n < 1000000）  
第二行：n个数x1、x2...xn，0 <= xi <= 1000000000

输出

如果数组中存在主元素，输出主元素；否则输出-1

样例输入

3
    1 2 2

样例输出

2

提示

使用O(n)的算法

很容易知道

如果无序，不能比较大小的算法，具体思想就是“在一个集合中，删除两个不同的数，则集合的主元素保持不变。”根据这个原理，可以很快求出主元素。只有最后剩下的元素才可能是主元素。

代码如下

#include<iostream>
    #include<stdio.h>
    using namespace std;
    int n,times,main_elem,x;
    int a[1000050];
    int main()
    {
    
       scanf("%d", &n);
       for (int i=0; i<n; i++)
       {
          scanf("%d", &x);
          a[i]=x;
       }
       times=0;
    
       for (int i=0; i<n; i++)
       {
           if (times==0)
           {
              main_elem=a[i];
              times++;  
           }else
           {
               if (main_elem==a[i]) times++;
                             else times--;
           }
       }
       times=0;
       for (int i=0; i<n; i++)
       {
           if (main_elem==a[i]) times++;
       }
       if (times>(n/2)) printf("%d", main_elem);
        else printf("%d", -1);
       
       return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关每日一练Day05：寻找多数元素

目录多数元素I 1、方法一 2、方法二 -------------------- 这道题来自LeetCode，下面我们来抽丝剥茧，细

落日映苍穹つ/ 2024年04月01日 17:01/ 0 赞/ 107 阅读

相关 287. Find the Duplicate Number 寻找重复元素

题目 Given an array nums containing n + 1 integers where each integer is between 1 and

红太狼/ 2023年06月10日 04:26/ 0 赞/ 17 阅读

相关主元素问题

主元素定义如果A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称X是A的主元素。问题要求如果A中的元素是可以排序的，设计一个时间复杂度为O（

小灰灰/ 2022年07月16日 00:19/ 0 赞/ 200 阅读

相关分治法实验-寻找第k小元素

问题描述随机生成含有n个不同元素的数组L（n≥10000），要求找出第k小的元素（k≤n），完成下面的任务：（1）设计一个基于排序选择算法程序，编程调试正确（排序

梦里梦外;/ 2022年07月16日 00:18/ 0 赞/ 197 阅读

相关 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 赞/ 190 阅读

相关寻找主元素

描述设A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称x是A的主元素。现在请你在一个数组中找到主元素。输入第一行：n（0 < n < 100

分手后的思念是犯贱/ 2022年06月13日 08:49/ 0 赞/ 197 阅读

相关 leetcode 645. Set Mismatch 寻找缺少元素

The set S originally contains numbers from 1 to n. But unfortunately, due to the data er

小鱼儿/ 2022年06月03日 05:39/ 0 赞/ 194 阅读

相关【LintCode 简单】46. 主元素

1.问题描述：给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。 2.样例：给出数组\[1,1,1,1,2,2,2\]，返回 1

- 日理万妓/ 2022年06月01日 01:44/ 0 赞/ 222 阅读

相关查找主元素

题目：已知一个整数序列A=(a0，a1，…，an-1)，其中0≤ai＜n(0≤i＜n)。若存在ap1=ap2=…=apm=x且m＞n/2(0≤pk＜n，1≤k≤m)，则称x为A

快来打我*/ 2021年12月24日 09:25/ 0 赞/ 400 阅读

相关求解数组中的主元素

原题：《数据结构与算法分析C++描述（第三版）》练习2.26 问题描述：大小为N的数组的主元素是出现次数超过N/2的元素。找到给定数组的主元素，若没有，应指出。完整代码：

曾经终败给现在/ 2021年12月12日 02:15/ 0 赞/ 257 阅读