将 1～1000 放在含有 1001 个元素的数组中，找出唯一的重复元素

[pwstrick]

Hash法

function findDup(array) {
  var len = array.length,
    newArr = [];
  if (!array || len < 1)
    return -1;
  for (var i = 0; i < len - 1; i++)
    newArr[i] = 0;
  for (i = 0; i < len; i++) {
    if (newArr[array[i] - 1] == 0) { 
      newArr[array[i] - 1] = 1; 
    } else {
      return array[i];
    }
  } 
  return -1;  //无重复元素则返回-1
}

异或法

function findDup3(array) {
  var len = array.length,
    result = 0;
  if (!array || len < 1)
    return -1;
  for (var i = 0; i < len; i++)
    result ^= array[i];
  for (i = 1; i < len; i++)
    result ^= i;
  return result;
}