题目地址
https://leetcode.com/problems/majority-element/description/
题目描述
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
思路
符合直觉的做法是利用额外的空间去记录每个元素出现的次数,并用一个单独的变量记录当前出现次数最多的元素。
但是这种做法空间复杂度较高,有没有可能进行优化呢? 答案就是用"投票算法"。
投票算法的原理是通过不断消除不同元素直到没有不同元素,剩下的元素就是我们要找的元素。
关键点解析
- 投票算法
代码
- 语言支持:JS,Python
Javascript Code:
/* * @lc app=leetcode id=169 lang=javascript * * [169] Majority Element * * https://leetcode.com/problems/majority-element/description/ * * algorithms * Easy (51.62%) * Total Accepted: 365.6K * Total Submissions: 702.5K * Testcase Example: '[3,2,3]' * * 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 * * */ /** * @param {number[]} nums * @return {number} */ var majorityElement = function(nums) { let count = 1; let majority = nums[0]; for(let i = 1; i < nums.length; i++) { if (count === 0) { majority = nums[i]; } if (nums[i] === majority) { count ++; } else { count --; } } return majority; };
Python Code:
class Solution: def majorityElement(self, nums: List[int]) -> int: count, majority = 1, nums[0] for num in nums[1:]: if count == 0: majority = num if num == majority: count += 1 else: count -= 1 return majorityLeetCode题解堆排序和快速排序
堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧
LeetCode题解斜着遍历遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…
LeetCode题解砝码的最小数量假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。输入示例:const weight = 100;输出示例:getResult(weight) // 15 其中7g的14个,2g的1个题解:```phpfunction getResult($weigh…
LeetCode题解93. 复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源:力扣(LeetCode)链接:https://le…
LeetCode题解886. 可能的二分法给定一组 N 人(编号为 1, 2, ..., N), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 a 和 b 的人归入同一组。当可以用这种方法将每个人分进两组时,返回 true;否则返回 false。 示例 1:输入:N = 4, disl…