["A","A","A","B","B","B"]
,即为 2,因为 A 和 B 的数量最多且一样["A", "A", "B", "C", "D"]
,间隔 n = 2 的时候,此时最小时间就是任务的长度明显是 4.sort((a, b) => a - b)
。⌊ n/2 ⌋
的元素。⌊ n/2 ⌋
意味着不大于 n/2
的最大正整数Math.floor()
或 parseInt()
取得⌊ n/2 ⌋
,则将它输出。依据题目可知,在输入数组中,有且只会有 1 种数字符合输出条件,即输出的值只会有一个。该解法的重点是,如何找到该元素在数组中出现的次数。如果直接继续用循环或 filter
方法,虽然可行,但是会因时间复杂度导致运行超时。因此,需要找到合理的解决办法。number
和 statistics
,分别用于存储结果元素和元素统计结果statistics
statistics
中找到符合边界值要求的元素2n
,因此,时间复杂度为 n/2
,因此,statistics
的占用空间最多 n/2
,空间复杂度为 nums=[3,1,1,2,1,3]
,我们可以考虑将其排序后,再利用两个指针查找目标值。排序后的数组如图所示,初始化时两个指针 i 和 j 分别指向数组的第一个元素(黄色箭头位置)和第二个元素((左)红色指针位置)。j - i
次。比较该元素出现次数是否满足题目元素,若满足,则将其输出, 若不满足则继续执行下一步。number
,用于存储结果元素其中需考虑特殊情况,如number
的初始值以及遍历中特殊情况的处理,详见代码。
sort()
方法,该方法在底层实现上依不同浏览器而有所差异。在 Chrome 浏览器中,使用了插入排序和快速排序结合的算法,具体使用情况与待排序数组的长度有关,一般情况下长度小于等于 10 的数组使用插入排序(可参考:深入浅出 JavaScript 的 Array.prototype.sort 排序算法)。假设此处考虑 Chrome 浏览器下使用快排作为排序算法的情况,则 sort()
耗时为 for
循环耗时 sort()
使用插入排序时空间复杂度为 count = 1
,数组的每一轮遍历中,判断两个指针所指元素是否相等,若相等则 count++
,否则 count--
。若此时 count === 0
,意味着相邻两元素值不相同,需将两指针分别向前移动一位并将 count
还原为初始值。majorityIndex
和 count
的值分别为 0
和 1
count
的值。若此时 count
为 0
,则将 majorityIndex
指针移动到当前 i
指针的位置,并重新将 count
设置为 1
majorityIndex
的元素