抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

23 | 面试题:求众数

169. 多数元素

解法一:暴力,两层循环,计算每个元素出现的次数,然后对比一下即可。

时间复杂度:O(N ²)

解法二:计数优先考虑 MAP,空间换时间,一遍遍历使用 MAP 计数,再对 MAP 中的元素进行比较,比较时次数少于 N。

时间复杂度:O(N) ,空间复杂度 O(N)

解法三:排序,排序后,最多数字一定是连续的,此时返回第 N/2的元素则一定是众数。

时间复杂度:O(NlogN) = 排序快排 O(NlogN)

class Solution {
fun majorityElement(nums: IntArray): Int {
Arrays.sort(nums)
return nums[nums.size/2]
}
}

解法四:分治。因为这里众数是一定存在的,所以逻辑上可以简化。

原理:和 pow 一样,分成两份,分别找左右两份中出现次数最多的数,如果 left中的众数 == right 中的众数,则众数返回任意一个即可。如果相等不成立,就比较左右众数的次数,返回次数最多的那个数。

class Solution {
fun majorityElement(nums: IntArray): Int {
return findElement(nums, 0, nums.size - 1)
}

fun findElement(nums: IntArray, lPos: Int, rPos: Int): Int {
//临界值 只有一个元素时直接返回
if (lPos == rPos) return nums[lPos]
//取中点
val mid = (rPos - lPos) / 2 + lPos

val left = findElement(nums, lPos, mid)
val right = findElement(nums, mid + 1, rPos)
//左右众数一致 随意返回一个
if (left == right) return left
//不一致则 比较count 大的则为众数
return if (count(left, nums, lPos, rPos) > count(right, nums, lPos, rPos)) { left } else { right }
}

fun count(num: Int, nums: IntArray, lPos: Int, rPos: Int): Int {
var count = 0
for (i in lPos..rPos) {
if (nums[i] == num) count++
}
return count
}
}

0条评论

发表评论