[Swift]LeetCode169.求众数|MajorityElement

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9715198.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

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

Example 2:

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

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

 1 class Solution {
 2     func majorityElement(_ nums: [Int]) -> Int {
 3         var res:Int = 0
 4         var counts:Int = 0
 5         for n in nums
 6         {
 7             if counts == 0
 8             {
 9                 res = n
10                 counts = 1
11             }
12             else if res == n
13             {
14                 counts += 1
15             }
16             else 
17             {
18                 counts -= 1
19             }
20         }
21         return res
22     }
23 }

24ms

 1 class Solution {
 2     func majorityElement(_ nums: [Int]) -> Int {
 3         var count = 1
 4         var pre = nums[0]
 5         var result = pre
 6         for i in 1..<nums.count {
 7             if count == 0 {
 8                 count = 1
 9                 pre = nums[i]
10                 result = nums[i]
11             } else if pre == nums[i] {
12                 count += 1
13             } else {
14                 count -= 1
15             }
16             
17         }
18         
19         return result
20          
21     }
22 }

20ms

 1 class Solution {
 2     func majorityElement(_ nums: [Int]) -> Int {
 3         guard nums.count > 0 else { return 0 }
 4         var candidate = nums[0]
 5         var times = 1
 6         var i = 1
 7         while i < nums.count {
 8             if times == 0 {
 9                 candidate = nums[i]
10                 times = 1
11                 i += 1
12                 continue
13             }
14             if nums[i] == candidate {
15                 times += 1
16             } else {
17                 times -= 1
18             }
19             i += 1
20         }
21         return candidate
22     }
23 }

28ms

 1 class Solution {
 2     func majorityElement(_ nums: [Int]) -> Int {
 3         var curNum = nums[0]
 4         var majority = 0;
 5         
 6         for num in 0..<nums.count {
 7             let val = nums[num]
 8             if curNum != val {
 9                 majority -= 1
10                 if majority < 1 {
11                     curNum = val
12                     majority = 1
13                 }
14             } else {
15                 majority += 1
16             }
17         }
18         return curNum;
19     }
20 }