leetCode 169. Majority Element 数组

简介:

169. Majority Element

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.


思路1:

使用map来处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class  Solution {
public :
     int  majorityElement(vector< int >& nums) {
         map< int int > record;
         for  ( int  i = 0; i < nums.size(); i++)
         {
             if  (record.find(nums[i]) == record.end())
             {
                 record.insert(pair< int int >(nums[i], 1));
                 if  (record[nums[i]] > nums.size() / 2)
                 {
                     return  nums[i];
                 }
             }
             else
             {
                 record[nums[i]] += 1;
                 if  (record[nums[i]] > nums.size() / 2)
                 {
                     return  nums[i];
                 }
             }
         }
         return  0;
     }
};

思路2:

采用双循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int  majorityElement(vector< int >& nums) {
     int  hit = 0;
     int  currentElem;
     for  ( int  i = 0; i < nums.size(); i++)
     {
         currentElem = nums[i];
         hit = 0;
         for  ( int  j = 0; j < nums.size(); j++)
         {
             if  (nums[j] == currentElem)
             {
                 hit++;
                 if  (hit > nums.size() / 2)
                 {
                     return  currentElem;
                 }
             }
         }
     }
     return  0;
}




本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1836477

相关文章
|
17小时前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
4 0
|
3天前
DAY-4 | 力扣 - 求自身以外数组的乘积:区间划分,左右累乘,巧求乘积
该文档是关于LeetCode上的一道题目“Product of Array Except Self”的题解。提供了两种解题方法,一是暴力破解,即计算所有数的乘积后再逐个除以当前元素;二是左右累乘法,通过两次遍历数组分别计算左侧和右侧元素的乘积,避免了除法操作。其中,左右累乘法更优,代码实现中展示了这种方法。
8 1
|
5天前
|
存储 算法
【数据结构与算法 | 基础篇】[数组专题]力扣88
【数据结构与算法 | 基础篇】[数组专题]力扣88
|
5天前
|
存储 C语言
Leetcode—— 删除排序数组中的重复项——C语言
Leetcode—— 删除排序数组中的重复项——C语言
|
5天前
|
算法 C语言
Leetcode----旋转数组 ------C语言篇
Leetcode----旋转数组 ------C语言篇
|
6天前
力扣2834. 找出美丽数组的最小和
力扣2834. 找出美丽数组的最小和
|
6天前
力扣421. 数组中两个数的最大异或值(字典树)
力扣421. 数组中两个数的最大异或值(字典树)
|
12天前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
16 2
|
12天前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
15 0
|
12天前
leetcode代码记录(两个数组的交集
leetcode代码记录(两个数组的交集
12 1