deduplicate

题目描述

实现一个数组去重函数 deduplicate()：

• 去除数组中的重复元素
• 如果是稀疏数组，保留一个空位
• 直接修改传入的数组（原地操作）
• 顺序不影响结果判定

本题考查 数组去重算法、稀疏数组处理 和 原地修改技巧。

核心知识点

1. 稀疏数组 (Sparse Array)

• 定义: 数组中某些索引位置没有元素（空位）
• 特征: Object.keys(arr).length < arr.length
• 创建方式: [1, , 3]、new Array(5)、delete arr[1]
• 遍历行为: forEach、map 等方法会跳过空位

2. 数组去重策略

• 简单去重: 使用 includes 检查是否存在
• Set 去重: 利用 Set 的唯一性特征
• Map 去重: 使用 Map 记录出现过的元素
• 原地修改: 不创建新数组，直接修改原数组

3. 原地操作技巧

• 数组截断: 修改 length 属性改变数组大小
• 元素覆盖: 用新元素覆盖原位置的元素
• 双指针: 读写指针分离实现原地压缩

代码实现

/**
 * @param {any[]} arr
 */
export default function deduplicate(arr) {
  const uniqueElements = []

  arr.forEach((el) => {
    if (!uniqueElements.includes(el))
      uniqueElements.push(el)
  })

  uniqueElements.forEach((el, idx) => {
    arr[idx] = el
  })
  // 如果是稀疏数组，保留一个空位
  arr.length = isSparse(arr)
    ? uniqueElements.length + 1
    : uniqueElements.length
}

function isSparse(arr) {
  return Object.keys(arr).length < arr.length
}

关键技术点

1. 稀疏数组判断

function isSparse(arr) {
  return Object.keys(arr).length < arr.length
}

// 原理解释
const sparse = [1, , 3, , 5]
console.log(sparse.length) // 5
console.log(Object.keys(sparse)) // ['0', '2', '4']
console.log(Object.keys(sparse).length) // 3
console.log(3 < 5) // true (是稀疏数组)

// 非稀疏数组
const dense = [1, 2, 3]
console.log(dense.length) // 3
console.log(Object.keys(dense).length) // 3
console.log(3 < 3) // false (不是稀疏数组)

2. 原地修改的原理

// 原始数组: [1, 2, 2, 3, 3, 3, 4]
// 去重后: [1, 2, 3, 4]

// 步骤分解
const arr = [1, 2, 2, 3, 3, 3, 4]
const unique = [1, 2, 3, 4]

// 覆盖原数组元素
unique.forEach((el, idx) => {
  arr[idx] = el // arr[0]=1, arr[1]=2, arr[2]=3, arr[3]=4
})

// 截断数组长度
arr.length = unique.length // arr = [1, 2, 3, 4]

3. 重复检测逻辑

// includes 方法的工作原理
arr.forEach((el) => {
  if (!uniqueElements.includes(el)) {
    // 线性搜索
    uniqueElements.push(el)
  }
})

// 等价的手动实现
arr.forEach((el) => {
  let found = false
  for (let i = 0; i < uniqueElements.length; i++) {
    if (uniqueElements[i] === el) {
      found = true
      break
    }
  }
  if (!found) {
    uniqueElements.push(el)
  }
})

4. 常见陷阱和坑点

• includes 性能: 对大数组效率低，考虑使用 Set
• 稀疏数组误判: 忘记检查稀疏数组导致空位丢失
• 类型相等: includes 使用严格相等比较
• NaN 处理: includes 可以正确处理 NaN
• 原地修改: 必须确保修改原数组而不是创建新数组

扩展思考

1. 性能优化版本 (Set)

function deduplicateOptimized(arr) {
  const seen = new Set()
  const uniqueElements = []

  arr.forEach((el) => {
    if (!seen.has(el)) {
      seen.add(el)
      uniqueElements.push(el)
    }
  })

  uniqueElements.forEach((el, idx) => {
    arr[idx] = el
  })

  arr.length = isSparse(arr)
    ? uniqueElements.length + 1
    : uniqueElements.length
}

// 时间复杂度: O(n)
// 空间复杂度: O(n)

2. 原地双指针版本

function deduplicateInPlace(arr) {
  if (arr.length <= 1)
    return

  const isSparseArray = isSparse(arr)
  let writeIndex = 0

  for (let readIndex = 0; readIndex < arr.length; readIndex++) {
    // 检查当前元素是否在前面出现过
    let isDuplicate = false
    for (let j = 0; j < writeIndex; j++) {
      if (arr[j] === arr[readIndex]) {
        isDuplicate = true
        break
      }
    }

    if (!isDuplicate) {
      arr[writeIndex] = arr[readIndex]
      writeIndex++
    }
  }

  arr.length = isSparseArray ? writeIndex + 1 : writeIndex
}

// 空间复杂度: O(1) (除了输入数组)
// 时间复杂度: O(n²) (但常数因子更小)

3. 支持自定义比较函数

function deduplicateCustom(arr, equalsFn = (a, b) => a === b) {
  const uniqueElements = []

  arr.forEach((el) => {
    const isDuplicate = uniqueElements.some(unique => equalsFn(el, unique))
    if (!isDuplicate) {
      uniqueElements.push(el)
    }
  })

  uniqueElements.forEach((el, idx) => {
    arr[idx] = el
  })

  arr.length = isSparse(arr)
    ? uniqueElements.length + 1
    : uniqueElements.length
}

// 使用示例：对象深度比较
const deepEquals = (a, b) => JSON.stringify(a) === JSON.stringify(b)
const objArr = [{ a: 1 }, { b: 2 }, { a: 1 }]
deduplicateCustom(objArr, deepEquals)
console.log(objArr) // [{a: 1}, {b: 2}]

4. 支持保留最后出现的元素

function deduplicateKeepLast(arr) {
  const seen = new Set()
  const uniqueElements = []

  // 从后往前遍历
  for (let i = arr.length - 1; i >= 0; i--) {
    if (!seen.has(arr[i])) {
      seen.add(arr[i])
      uniqueElements.unshift(arr[i]) // 插入到前面
    }
  }

  uniqueElements.forEach((el, idx) => {
    arr[idx] = el
  })

  arr.length = isSparse(arr)
    ? uniqueElements.length + 1
    : uniqueElements.length
}

// 测试
const arr = [1, 2, 3, 2, 1, 4]
deduplicateKeepLast(arr)
console.log(arr) // [3, 2, 1, 4] (保留最后出现的位置)

5. 统计重复次数版本

function deduplicateWithCount(arr) {
  const countMap = new Map()

  // 统计频次
  arr.forEach((el) => {
    countMap.set(el, (countMap.get(el) || 0) + 1)
  })

  // 收集唯一元素和计数
  const uniqueElements = Array.from(countMap.keys())

  uniqueElements.forEach((el, idx) => {
    arr[idx] = el
  })

  arr.length = isSparse(arr)
    ? uniqueElements.length + 1
    : uniqueElements.length

  // 返回重复统计信息
  return Object.fromEntries(countMap)
}

// 使用示例
const arr = [1, 2, 2, 3, 3, 3]
const counts = deduplicateWithCount(arr)
console.log(arr) // [1, 2, 3]
console.log(counts) // {1: 1, 2: 2, 3: 3}