2020-05-14: 前端算法-找到出现两次的元素

15. 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）,
    其中有些元素出现两次而其他元素出现一次,找到所有出现两次的元素

[要求Tc: O(n) Sc:O(1)]

例:
输入:
  [4,3,2,7,8,2,3,1]

  // [7,3,2,4,8,2,3,1]
  // [3,3,2,4,8,2,7,1]
  // [2,3,3,4,8,2,7,1]
  // [2,3,3,4,1,2,7,8]
  // [1,2,3,4,3,2,7,8]

输出:
  [2,3]

主要麻烦的点在于空间需要Sc: O(1)

const appearTwice = function(ary) {
  const aryLen = ary.length;
  for (let i = 0; i < aryLen; i += 1) {
    const item = ary[i];
    if (ary[item-1] !== ary[i]) {
      [ary[item-1], ary[i]] = [ary[i], ary[item-1]];
      i --;
    }
  }
  for (let i = 0; i < aryLen; i += 1) {
    const item = ary[i];
    if (item - 1 !== i) {
      ary.push(item);
    }
  }
  return ary.slice(aryLen);
}

const ary = [4,3,2,7,8,2,3,1];

console.log(appearTwice(ary));