数据结构与算法（数组） --javascript语言描述

找出数组中重复的数字

n个数字，且数字都在0到n-1范围内
思路：从头到尾扫描数组每个数字，当扫描到下标为i的数字m时，首先比较m是不是等于i,如果是，继续扫描；如果不是，再拿m和第m个数字进行比较。如果他们相等，就找到第一个重复数字，如果不相等，交换两者位置。接下来重复上述过程，直到找到第一个重复数字。

function Find(arrNumbers) {
  for (var i = 0; i < arrNumbers.length; i++) {
    while(arrNumbers[i]!==i) {
      if(arrNumbers[i] === arrNumbers[arrNumbers[i]]) {
        return arrNumbers[i];
      }
      let temp = arrNumbers[i];
      arrNumbers[i] = arrNumbers[temp];
      arrNumbers[temp] = temp;
    }
  }
}
let arr = [2,3,1,0,2,5,3];
console.log(Find(arr));

代码中尽管有一个两重循环，但是每个数字最多只要交换两次就能够找到属于它自己的位置，因此总的时间复杂度是O(n)。另外，所有的操作步骤都是在输入数组上进行的，不需要额外分配内存，因此空间复杂度为O(1)。

不修改数组找出重复的数字（二分查找）

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但是不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。

思路1：
由于不能修改输入的数组，我们可以创建一个长度为n+1的辅助数组，然后逐一把原数组的每个数字复制到辅助数组。如果原数组中被复制的数字是m，则把它复制到辅助数组中下标为m的位置。如果下标为m的位置上已经有数字了，则说明该数字重复了。由于使用了辅助空间，故该方案的空间复杂度是O(n)。

思路2：
由于思路1的空间复杂度是O(n)，因此我们需要想办法避免使用辅助空间。我们可以想：如果数组中有重复的数，那么n+1个0~n范围内的数中，一定有几个数的个数大于1。那么，我们可以利用这个思路解决该问题。

我们把从1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1~n。如果1~m的数字的数目等于m，则不能直接判断这一半区间是否包含重复的数字，反之，如果大于m，那么这一半的区间一定包含重复的数字；如果小于m，另一半m+1~n的区间里一定包含重复的数字。接下来，我们可以继续把包含重复的数字的区间一分为二，直到找到一个重复的数字。

由于如果1~m的数字的数目等于m，则不能直接判断这一半区间是否包含重复的数字，我们可以逐步减少m，然后判断1~m之间是否有重复的数，即，我们可以令m=m-1，然后再计算1~m的数字的数目是否等于m，如果等于m，再令m=m-1，如果大于m，则说明1~m的区间有重复的数，如果小于m，则说明m+1~n有重复的数，不断重复此过程。

function Find(arrNumbers) {
  let start = 1;
  let end = arrNumbers.length - 1;
  while(end >= start) {
    let middle = parseInt((end - start)/2) + start;
    let count = countRange(arrNumbers,start,middle);
    if(end == start) {
      if(count > 1) {
        return start;
      }
      else {
        break;
      }
    }
    if(count > (middle - start + 1)) {
      end = middle;
    }
    else {
      start = middle + 1;
    }
  }
  return -1;
}

function countRange(arrNumbers,start,end) {
  let count = 0;
  for (var i = 0; i < arrNumbers.length; i++) {
    if(arrNumbers[i] >=start && arrNumbers[i] <= end) {
      count++;
    }
  }
  return count;
}

let arr = [2,3,5,4,3,2,6,7];
console.log(Find(arr));

上述代码按照二分查找的思路，如果输入长度为n的数组，那么函数countRange最多将被调用O(logn)次，每次需要O(n)的时间，因此总的时间复杂度是O(nlogn)。和前面提到的需要o(n)的辅助空间的算法比，这种算法相当于以时间换空间。

二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

function Find(num,arr) {
  let found = false;
  let row = 0;
  let col = arr[0].length - 1;
  while(row < arr.length && col >= 0){
    if(arr[row][col] == num) {
      found = true;
      break;
    }
    else if(arr[row][col] > num) {
      col--;
    }
    else {
      row ++;
    }
  }
  return found;
}

let arr = [
  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]
];

console.log(Find(7,arr));