统计数组中的元素

645. 错误的集合

思路

本质上就是一个数学问题，
(原数组的和-去掉重复的数据的数组和)=重复的数字
(从1到数组的长度length的数据的和(1+2+…+length))-(去掉重复的数据的数组和)=缺失的数字

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
  let a = getSum(nums) - getSum([...new Set(nums)])
  let b = calcSum(nums.length) - getSum([...new Set(nums)])
  return [a, b]
};
function getSum(arr) {
  let sum = 0;
  for(let i = 0; i < arr.length; i ++) {
    sum += arr[i]
  }
  return sum;
}
function calcSum(n) {
  let sum = 0;
  for(let i = 1; i <= n; i ++) {
    sum += i;
  }
  return sum;
}

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

697. 数组的度

思路

理解题意：先找众数，如果只有1个则返回众数的个数，如果有多个，则返回区间最小的长度。

先用map存储数字的总数和下标；
经过两次遍历，得到结果

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findShortestSubArray = function(nums) {
  const map = {};
  for(let i = 0; i < nums.length; i ++) {
    let cur = nums[i];
    if (map[cur]) {
      map[cur].count += 1;
      if (map[cur].idxs.length > 1) {
        map[cur]['idxs'][1] = i
      } else {
        map[cur].idxs.push(i);
      }
    } else {
      map[cur] = {
        count : 1,
        idxs: [i]
      }
    }
  }
  let max = 0, keys = []
  for(let [key, {count}] of Object.entries(map)) {
    if (count > max) {
      max = count
      keys = [key]
    } else if (count == max) {
      keys.push(key)
    }
  }
  if (keys.length == 1) {
    let [start, end] =  map[keys[0]].idxs
    return end ? (end - start + 1) : 1
  }
  let ret = nums.length;
  for(let key of keys) {
    let {count, idxs:[start, end]} = map[key]
    ret = Math.min(ret, end ? (end - start + 1) : 1)
  }
  return ret;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)

448. 找到所有数组中消失的数字

思路

创建一个长度为n+1长度的结果数组；

第一次遍历将存在的数字对应坐标上赋值；

第二次对结果数组取反，将空位上赋值为当前的idx，为缺失的数字；

然后对结果数组过滤掉空值；

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
  let res = []
  for(let i = 0; i < nums.length; i ++) {
    let cur = nums[i];
    res[cur] = 1;
  }
  for(let i = 1; i <= nums.length;i++) {
    let cur = res[i];
    if (cur) {
      res[i] = undefined
    } else {
      res[i] = i;
    }
  }
  return res.filter(Boolean);
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

442. 数组中重复的数据

思路

由于索引和对应值有关系，第1次出现可以将当前值对应的索引位置的值取反，当第二次遍历到该值索引时为负数。

eg: [1,2,3,4,5,2]

第一次遍历

[1,2,3,4,5] => [-1, -2, -3, -4, -5]

第二次遍历

[-1, -2, -3, -4, -5] => [-1, 2, -3, -4, -5]

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function(nums) {
  const res = [];
  for(let i = 0; i < nums.length; i ++) {
    let cur = Math.abs(nums[i]);
    if (nums[cur-1] > 0) {
      nums[cur-1] *= -1
    } else {
      res.push(cur)
    }
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

274. H 指数

思路

默认h为文章数，对引用量排序，如果小于h，将h—

代码

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
  citations = citations.sort((a, b) => a - b);
  let len = citations.length, res = len;
  for(let i = 0; i < len; i ++) {
    let cur = citations[i];
    if (cur < res) {
      res -= 1;
    }
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28nlogN%29)
空间复杂度 #card=math&code=O%281%29)

41. 缺失的第一个正数