“LeetCode-比较字符串最小字母出现频次”代码优化记录

525 阅读5分钟

起因

我昨天刷到一道 LeetCode,成功提交后发现执行时间还是有点儿太长,才打败了 5% 的 JS 用户,这可不行,我得自我探索和突破一下,一定是我算法和写法太 low 了!

那道题目是这样的:

(图片)1170. 比较字符串最小字母出现频次
想动手试试的可以点这里:leetcode 题目 - 1170. 比较字符串最小字母出现频次

我的思路是这样,很常规:

  1. 写一个函数用来计算最小字母的出现频次

  2. 新建一个空数组 answer和计数变量 time

  3. 双重遍历 querieswords ,分别对这两个数组的数组项进行频次的计算,进行对比后,符合条件的则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]]
        }
    }
}

提交了三次,两次失败,失败原因是某些测试用例超过了时间限制,我用了一些方案修改后提交第三次才成功:

  1. 将字符串转为数组时,使用 s.split('') 比使用 Array.from(s) 更加高效。
  2. 一开始使用 Array.map 进行循环,改成 Array.forEach 后更加高效。
  3. 使用 for 循环来替代了 Array.forEach,这只是为了优化算法,在符合某种条件的情况下,不需要继续循环,使用 for 可以跳出循环体。
  4. 一开始是在双重循环里直接拿 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 用户了。

回想一下,原来为什么还要弄个对象来保存?

用对象来保存,可以知道最小的字符是什么,一共出现了几次。但是这道题其实并没有这个必要,不需要知道什么是最小的字符。

除了双重遍历,是否有更好的方法呢?

  1. 先分别对两个数组元素计算出最小字符出现的频次,存入到新数组(queriesCount / wordsCount)中
  2. wordsCount 中的数组进行降序排列
  3. 尝试使用二分法,进行遍历对比:拿 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 用户了!

延伸

说明:以下代码并没有经过大量的测试用例测试以及性能测试

如何找出字符串中出现次数最多的字符

例如:

  1. 输入 'abfeigeaabjgeba',结果应该返回 a。解释:因为 a 出现了 4 次,其他字符出现的次数都小于 4 次。
  2. 输入 'bfeigeaabjgeba',结果应该返回 abe。解释因为 abe 都出现了 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 且最小的字符

例如:

  1. 输入 'abfeigeaabjgeba',结果应该返回 a。解释:因为 a 出现了 4 次,其他字符出现的次数都小于 4 次。
  2. 输入 'bfeigeaabjgeba',结果应该返回 a。解释因为 abe 都出现了 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)
}