Leetcode 1781 传统遍历方法超时

Question

老师，我做了今日一题，还是用的朴素的遍历方法，因为直观直接, 哈哈哈,leetcode是报了超时，然后我也看了您的代码，没领会。。。

/**
 * @param {string} s
 * @return {number}
 */
var beautySum = function(s) {
    let res = 0; // 存放结果
    for( let i = 0; i < s.length; i ++ ){
        // [i, j]之前的美丽值
        let map = {};
        for( let j = i; j < s.length; j ++ ){
            // [i, j]
            // 得到出现频率最高的次数与频率最低的次数
            for( let k = i; k <= j; k ++ ){
                let nowCh = s[k];
                map[nowCh] = map[nowCh] || 0;
                map[nowCh]++;

            } // for k

            // 在map中找到 => 出现频率最高的次数与频率最低的次数
            let arr = Object.entries(map);
            arr.sort((a, b)=>b[1]-a[1]); // 排序
            res += (arr[0][1] - arr[arr.length-1][1]);

            map = {}; // 处理完 [i, j]这一段子字符串后，map清空
        } // for j

    } //for i
    return res;
};

==========================更新1 =================================

    let res = 0; // 存放结果
    for( let i = 0; i < s.length; i ++ ){
        // [i, j]之前的美丽值
        let map = {};
        for( let j = i; j < s.length; j ++ ){
            let nowCh = s[j];
            map[nowCh] = map[nowCh] || 0; // 对nowCh未出现的情况初始化为0
            map[nowCh] ++;

            // 在map中找到 => 出现频率最高的次数与频率最低的次数
            let arr = Object.entries(map);
            arr.sort((a, b)=>b[1]-a[1]); // 排序
            res += (arr[0][1] - arr[arr.length-1][1]);

        } // for j

    } //for i
    return res;
};

Answer 1

liuyubobobo 2022-12-13 17:48:38

你的算法即使不计算 map 的复杂度，也至少是 n^3 的级别。500^3 = 1.25*10^8，肯定超时。（回忆一下，在这个课程中我介绍过，一般 10^7 这个级别已经撑死了。）

在你的算法中，i 是遍历的子串的起始位置；j 是遍历的子串的终止位置。k 每次在 [i, j] 之间再遍历一次，实际上，每次 j 向后移动 1，即考虑 [i, j + 1] 的时候，k 没必要从 i 重新遍历一次，直接把 j + 1 位置的信息添加到 [i, j] 子串的信息上就好了。

顺着这个思路再试试看？

继续加油！：）

• 提问者 甲骨文_0001 #1

  老师，按照您说的我更改下，方法我改在了上面的编辑框，其实就是把for k这层循环给去除掉，直接用2层循环，依然是 对内层for循环，我每遍历一个j索引，我更新一下map表，然后再用语言的能力把map表中的key,val转成数组，再排序，再计算美丽值，再更新到res中。现在leetcode是通过了，但也用了9秒时间。。。在内层for j循环中，主要是用了系统的内带方法才有了高性能的运行，但是从本质上看，Object.entries(map)转数组，再sort排序，内部肯定有循环，所以依然是3层循环。老师，就我目前的代码，还能再优化吗: )

• liuyubobobo 回复 提问者 甲骨文_0001 #2

  首先要明确一点的是，现在你的代码已经是 O(n^2) 的了。这是因为 map 里最多只能有 26 个元素，所以对 map 的 sort 是 O(1) 的（和数据规模 n 无关。）
  
  所以，现在你遇到的问题是语言相关的问题，而非算法问题了。以下代码可以在 1s 时间内通过。主要的更改是把 map 修改成了 Array 类型。在大多数语言中，数组都会比更复杂的结构快，但是具体会快多少，是语言相关的。另外，我这样修改代码避免了你的代码中从 map 到 arr 的转换。这步转换因为有内存操作，所以也是耗时的。但是，我坚信在 C++ 或者 Java 中，这两种写法性能差距不会这么大（15 倍）。这就是为什么我不建议使用解析型语言作算法，尤其是非常性能敏感的算法。并不是不能做，但是你需要考虑很多和算法无关，和语言相关的问题。实际上，我的代码和你的代码逻辑是基本一致的。
  
  ```
  var beautySum = function(s) {
  
      let res = 0; // 存放结果
      for( let i = 0; i < s.length; i ++ ){
          // [i, j]之前的美丽值
          let map = new Array(26).fill(0);
          for( let j = i; j < s.length; j ++ ){
              let c = s[j].charCodeAt(0) - 'a'.charCodeAt(0);
              map[c] ++;
  
              let maxv = Math.max.apply(null, map.filter(Boolean))
              let minv = Math.min.apply(null, map.filter(Boolean))
  
              res += maxv - minv
          } // for j
  
      } //for i
      return res;
  };
  ```
  
  另：因为我不是 js 专家，我不排除有更快的这个逻辑的 js 的写法。

• 提问者 甲骨文_0001 回复 liuyubobobo #3

  谢谢老师，您很专业，我受益匪浅: ）