关关的刷题日记 01 – Leetcode 169. Majority Element 方法 1

关关的刷题日记01 – Leetcode 169. Majority Element 方法1

引言

从去年圣诞节近乎于零基础开始刷题,到现在转眼间十个月过去了,刷了有200道题目了。现在一边复习以前的题目把思路和AC代码写出来,一边继续往前刷刷刷。尤其对于零基础小白来说,这条路不是那么轻松和一帆风顺,需要为止付出大量的时间和精力, 另外还有漫长努力过程中的那份坚持,当然苦尽甘来的滋味是最最让人难忘的。最重要的是你方向明确,你从未停止,你在那一天来临之前就做好了充足准备!也欢迎大家多多交流!

Leetcode的题目是按照tag来划分的。每个tag的题目会分为easy、medium、hard三个级别的难度,每道题目后面有接收率。从难度级别低且acceptence高的题目开始刷起。我第一遍只刷500题号以内easy和medium的题目,用C++刷。题目是刷不完的,重在总结和理解吧,hard的题目一般面试也考不到,等以后进阶了再刷hard的题目了。先从array tag开始!

开始

题目

  1. 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.

题目的意思是有一个数组,数组中有一个数出现的次数大于数组长度的一半,让找出这个数。

思路

最简单的方法就是对数组进行排序,排序之后的数组的中位数就是目标值。 但是注意冒泡、选择等排序方法都超时了,复杂度O(n2)太高了,所以用sort快排。时间复杂度O(nlogn)。


class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};

明天更新这道题的方法2和方法3.

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。 同时请,关注我们的公众号,获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。

图片

展开全文
相关主题
Top