起因
我昨天刷到一道 LeetCode,成功提交后发现执行时间还是有点儿太长,才打败了 5% 的 JS 用户,这可不行,我得自我探索和突破一下,一定是我算法和写法太 low 了!
那道题目是这样的:
想动手试试的可以点这里:leetcode 题目 - 1170. 比较字符串最小字母出现频次我的思路是这样,很常规:
-
写一个函数用来计算最小字母的出现频次
-
新建一个空数组
answer
和计数变量time
-
双重遍历
queries
和words
,分别对这两个数组的数组项进行频次的计算,进行对比后,符合条件的则time+1
,遍历完内层后,把最后的计数值推入answer
中,遍历完外层后,返回answer
以下是我的代码实现:
/**
* @param {string[]} queries
* @param {string[]} words
* @return {number[]}
*/
var numSmallerByFrequency = function (queries, words) {
const answer = []
// 双重遍历开始
for (let i = 0; i < queries.length; i++) {
// 计数器 time 用来记录 queries[i] 与 words 数组每项对比后符合条件的个数
let times = 0
// 计算 queries[i] 最小字母重复出现的频次
const queries_statisticsFrequency = statisticsFrequency(queries[i])
for (let j = 0; j < words.length; j++) {
// 计算 words[j] 最小字母重复出现的频次
const words_statisticsFrequency = statisticsFrequency(words[j])
if (queries_statisticsFrequency < words_statisticsFrequency) {
times += 1
}
}
answer.push(times)
}
return answer
};
/**
* 此函数用来求得最小字母的出现频次
* 1. 先将字符串 s 转为数组,并按字母顺序排列
* 2. 遍历数组,求得最小字母重复出现的频次,并返回频次数
*/
var statisticsFrequency = function (s) {
let frenquencyObj = {}
const arrayFromS = s.split('').sort()
for(let i=0;i<arrayFromS.length;i++){
const value = frenquencyObj[arrayFromS[i]]
frenquencyObj[arrayFromS[i]] = value ? value+1 : 1
/** 如果下一个字母和目前的这个字母不一样,
* 则说明最小字母重复出现的频次已累计完毕,可以直接返回值了
*/
if(arrayFromS[i] !== arrayFromS[i+1]){
return frenquencyObj[arrayFromS[0]]
}
}
}
提交了三次,两次失败,失败原因是某些测试用例超过了时间限制,我用了一些方案修改后提交第三次才成功:
- 将字符串转为数组时,使用
s.split('')
比使用Array.from(s)
更加高效。 - 一开始使用
Array.map
进行循环,改成Array.forEach
后更加高效。 - 使用
for
循环来替代了Array.forEach
,这只是为了优化算法,在符合某种条件的情况下,不需要继续循环,使用for
可以跳出循环体。 - 一开始是在双重循环里直接拿
statisticsFrequency(queries[i])
与statisticsFrequency(words[j])
写在if
语句里进行对比,导致每次都要重复计算这两个值。后来把值提到if
之外计算,并赋值给变量,拿变量进行对比,也节省了一些时间。
优化
如何找出字符串中最小的字符出现的次数
/**
* 此函数用来求得最小字母的出现频次
* 1. 先将字符串 s 转为数组,并按字母顺序排列
* 2. 遍历数组,求得最小字母重复出现的频次,并返回频次数
*/
var statisticsFrequency = function (s) {
const arrayFromS = s.split('').sort()
let time = 0
for (let i = 0; i < arrayFromS.length; i++) {
time += 1
if (arrayFromS[i] !== arrayFromS[i + 1]) {
return time
}
}
}
这么一改,终于可以打败 7.69% 的 JS 用户了。
回想一下,原来为什么还要弄个对象来保存?
用对象来保存,可以知道最小的字符是什么,一共出现了几次。但是这道题其实并没有这个必要,不需要知道什么是最小的字符。
除了双重遍历,是否有更好的方法呢?
- 先分别对两个数组元素计算出最小字符出现的频次,存入到新数组(
queriesCount
/wordsCount
)中 - 对
wordsCount
中的数组进行降序排列 - 尝试使用二分法,进行遍历对比:拿
queriesCount
的数组项和被一次次二分的wordsCount
进行对比
/**
* @param {string[]} queries
* @param {string[]} words
* @return {number[]}
*/
var numSmallerByFrequency = function (queries, words) {
const answer = []
// 计算 queries 数组元素最小字符出现的频次,并存到一个新数组中
const queriesCount = queries.map(item => {
return statisticsFrequency(item)
})
// 计算 words 数组元素最小字符出现的频次,降序排列后,存到一个新数组中
const wordsCount = words.map(item => {
return statisticsFrequency(item)
}).sort(compare).reverse()
// 利用二分法,进行遍历对比
queriesCount.forEach(item => {
let front = 0,
end = wordsCount.length,
mid
while (front <= end) {
mid = parseInt((front + end) / 2)
if (mid !== front && mid !== end) {
// 二分法
if (item >= wordsCount[mid]) {
end = mid
} else {
front = mid
}
}
// 当查找 wordsCount[0] 时,如果 item >= wordsCount[mid],说明没有符合小于条件的情况,应该返回 0
else if(mid === 0 && item >= wordsCount[mid]) {
answer.push(0)
return
}
else {
// 由于 mid 记录的其实是数组的下标,下标从 0 开始,所以这里返回时应该 +1
answer.push(mid + 1)
return
}
}
})
return answer
};
// 用于数组项排序
var compare = function (a,b){
return a-b
}
这下子好了,击败了 80.77% 的 JS 用户了!
延伸
说明:以下代码并没有经过大量的测试用例测试以及性能测试
如何找出字符串中出现次数最多的字符
例如:
- 输入
'abfeigeaabjgeba'
,结果应该返回a
。解释:因为a
出现了 4 次,其他字符出现的次数都小于 4 次。 - 输入
'bfeigeaabjgeba'
,结果应该返回abe
。解释因为a
、b
、e
都出现了 3 次,其他字符出现的次数都小于 3 次。
代码实现如下:
var maxTimeCharacter = function (s) {
let frenquencyObj = {},
maxTime = 0,
character = ''
const arrayFromS = s.split('').sort()
arrayFromS.forEach(item => {
// 把字符当做 key,把出现的次数当做 value
let value = frenquencyObj[item]
frenquencyObj[item] = value ? (++value) : 1
if (maxTime <= value) {
maxTime = value
if (character !== item) {
character += item
} else {
character = item
}
}
})
return character
}
如何找出字符串中出现次数大于 1 且最小的字符
例如:
- 输入
'abfeigeaabjgeba'
,结果应该返回a
。解释:因为a
出现了 4 次,其他字符出现的次数都小于 4 次。 - 输入
'bfeigeaabjgeba'
,结果应该返回a
。解释因为a
、b
、e
都出现了 3 次,其他字符出现的次数都小于 3 次,但是a
字符是其中最小的字符
代码实现如下:
var moreTimeCharacter = function (s) {
let frenquencyObj = {},
maxTime = 0,
character = ''
const arrayFromS = s.split('').sort()
arrayFromS.forEach(item => {
// 把字符当做 key,把出现的次数当做 value
let value = frenquencyObj[item]
frenquencyObj[item] = value ? (++value) : 1
if (maxTime <= value) {
maxTime = value
if (character !== item) {
character += item
} else {
character = item
}
}
})
return character.charAt(0)
}