Skip to content

Latest commit

 

History

History
108 lines (90 loc) · 3.38 KB

697-数组的度.md

File metadata and controls

108 lines (90 loc) · 3.38 KB

697-数组的度

原题

给定一个非空且只包含非负数的整数数组  nums,数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与  nums  拥有相同大小的度的最短连续子数组,返回其长度。

输入:nums = [1,2,2,3,1] 输出:2 解释: 输入数组的度是 2 ,因为元素 1 和 2 的出现频数最大,均为 2 。 连续子数组里面拥有相同度的有如下所示: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] 最短连续子数组 [2, 2] 的长度为 2 ,所以返回 2 。

输入:nums = [1,2,2,3,1,4,2] 输出:6 解释: 数组的度是 3 ,因为元素 2 重复出现 3 次。 所以 [2,2,3,1,4,2] 是最短子数组,因此返回 6 。

这种题感觉还挺好写的,首先用 reduce 来计算所有数字的频度, 然后找到最大数字的频度,直接通过在数组中找到该数字的 lastIndexOf - indexOf 就是最短连续子数组的长度了,时间复杂度就是 O(n)

如果有多个数字出现的频次一样,就需要使用 for 循环了, 然后在 for 循环里面还要使用 indexOf/lastIndexOf , 复杂度可能就是 O(n^2) 了

const findShortestSubArray = function (nums) {
  // 算出所有数字出现的频次
  let calc = nums.reduce((memo, current) => {
    memo[current] ? memo[current]++ : (memo[current] = 1);
    return memo;
  }, {});

  // 计算一下出现最多的频次数是多少
  let keys = Object.keys(calc);
  let max = 0; // 用来比较的
  for (const key of keys) {
    if (calc[key] >= max) {
      max = calc[key];
    }
  }

  // 把出现频次最多的数字添加到一个数组里面去
  let arr = []; // 记录出现频次最多的数
  for (const key of keys) {
    if (calc[key] === max) {
      arr.push(key);
    }
  }

  // 从上面的那个数组中来计算最小的连续子数组
  let res = Infinity;
  for (const item of arr) {
    // 因为在第一部计算所有数字的频次是加入到一个对象中,而对象的减值会转换成字符串,所以这里使用+来转换回来
    let len = nums.lastIndexOf(+item) - nums.indexOf(+item);
    if (len < res) {
      res = len;
    }
  }

  // 因为是连续子数组的长度,而 lastIndexOf - indexOf 是索引的差值,所以还要加上 1
  return res + 1;
};

let nums = [4, 5, 1, 2, 2, 3, 1];
let result = findShortestSubArray(nums);
console.log(result);

优化优化,就是在第一次遍历的时候,就存储当前字段的次数,indexOf 和 lastIndexOf,这样的话,就只需要两次循环就可以了

const findShortestSubArray = function (nums) {
  const mp = {};

  for (const [i, num] of nums.entries()) {
    if (num in mp) {
      mp[num][0]++;
      mp[num][2] = i;
    } else {
      // 第一个值是出现的次数,第二个值出现的是首次出现的位置,第三个值是最后一次出现的位置
      mp[num] = [1, i, i];
    }
  }

  let maxNum = 0,
    minLen = 0;
  for (const [count, left, right] of Object.values(mp)) {
    if (maxNum < count) {
      maxNum = count;
      minLen = right - left + 1;
    } else if (maxNum === count) {
      if (minLen > right - left + 1) {
        minLen = right - left + 1;
      }
    }
  }
};

let nums = [];
let result = findShortestSubArray(nums);
console.log(result);