LeetCode刷算法题 - 169. Majority Ele

2018-05-04  本文已影响143人  蓝色小石头

写在前面:

程序员分两种,会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的,程序猿们都懂的,现在最权威流行的刷题平台就是 LeetCode。

LeetCode原题链接

string - C++ Reference

C++中int与string的相互转换

C++ Map常见用法说明

Question:

Difficulty:Easy Tag:Array

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.

Example:

Input: [3,2,3]
Output: 3
Input: [2,2,1,1,1,2,2]
Output: 2

Solution:

以下代码皆是本人用 C++写的,觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教,多多学习。

A1、运用哈希特性

算法时间复杂度 O(n),Runtime: 16 ms,代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间,可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> map;
        
        for (int i=0; i<nums.size(); i++) {
            int key = nums[i];
            if (map.find(key) == map.end()) {
                map[key] = 1;
            } else{
                map[key] = map[key]+1;
            }
            if (map[key] > nums.size()/2) {
                return nums[i];
            }
        }
        return 0;
    }
};
A2、渐进排除式解法

算法时间复杂度 O(n),Runtime: 10 ms,代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间,可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majorIndex = 0, cnt = 1;
        for(int i=0; i<nums.size(); ++i) {
            if(nums[majorIndex] == nums[i])
                cnt++;
            else
                cnt--;
            
            if(cnt==0) {
                majorIndex = i;
                cnt = 1;
            }
        }
        return nums[majorIndex];

    }
};

引用相关

LeetCode 官网

上一篇下一篇

猜你喜欢

热点阅读