有没有数组整数排序的替代方法？解决查找唯一数时调用栈溢出问题

你遇到的调用栈溢出错误，是因为部分旧版JS引擎的Array.sort()方法底层采用递归实现的快速排序，当处理长度极大的数组时，递归深度超过JS引擎预设的调用栈上限，就会抛出该错误。

同时你的需求是查找数组中唯一的不同数字，完全不需要依赖排序实现，可以用更高效、无栈溢出风险的方案完成：

方案1：直接遍历查找（性能最优） #

题目限定只有1个唯一不同的数字，其余数字完全相同，因此可以先通过前3个元素确定出重复的基准值，再遍历一次数组找到和基准值不同的元素即可，时间复杂度O(n)，空间复杂度O(1)：

function findUniq(arr) {
  // 确定多数重复的基准值
  let base
  if (arr[0] === arr[1]) {
    base = arr[0]
  } else {
    base = arr[2] === arr[0] ? arr[0] : arr[1]
  }
  // 遍历找唯一不同值
  for (const num of arr) {
    if (num !== base) return num
  }
}

方案2：计数统计（通用性更强） #

如果后续需要适配存在多个唯一值的场景，可以用Map统计每个数字的出现次数，返回出现次数为1的数字即可：

function findUniq(arr) {
  const count = new Map()
  for (const num of arr) {
    count.set(num, (count.get(num) || 0) + 1)
  }
  for (const [num, freq] of count.entries()) {
    if (freq === 1) return num
  }
}

如果其他场景需要用到排序功能又要避免栈溢出，可以用迭代实现的排序算法替换原生递归版sort，示例为迭代版快速排序：

function iterativeQuickSort(arr) {
  const stack = [[0, arr.length - 1]]
  while (stack.length) {
    const [left, right] = stack.pop()
    if (left >= right) continue
    // 选最右元素为基准
    const pivot = arr[right]
    let partitionIdx = left - 1
    for (let i = left; i < right; i++) {
      if (arr[i] < pivot) {
        partitionIdx++
        [arr[partitionIdx], arr[i]] = [arr[i], arr[partitionIdx]]
      }
    }
    partitionIdx++
    [arr[partitionIdx], arr[right]] = [arr[right], arr[partitionIdx]]
    // 左右分区入栈
    stack.push([left, partitionIdx - 1], [partitionIdx + 1, right])
  }
  return arr
}

内容的提问来源于stack exchange，提问作者Pexate