數(shù)據(jù)結(jié)構(gòu)與算法（數(shù)組） --javascript語言描述

MycLambert 發(fā)布于2019-08-26 11:43 / 2742人閱讀

摘要：如果下標(biāo)為的位置上已經(jīng)有數(shù)字了，則說明該數(shù)字重復(fù)了。二維數(shù)組中的查找在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

找出數(shù)組中重復(fù)的數(shù)字

n個數(shù)字，且數(shù)字都在0到n-1范圍內(nèi)
思路：從頭到尾掃描數(shù)組每個數(shù)字，當(dāng)掃描到下標(biāo)為i的數(shù)字m時，首先比較m是不是等于i,如果是，繼續(xù)掃描；如果不是，再拿m和第m個數(shù)字進行比較。如果他們相等，就找到第一個重復(fù)數(shù)字，如果不相等，交換兩者位置。接下來重復(fù)上述過程，直到找到第一個重復(fù)數(shù)字。

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));

代碼中盡管有一個兩重循環(huán)，但是每個數(shù)字最多只要交換兩次就能夠找到屬于它自己的位置，因此總的時間復(fù)雜度是O(n)。另外，所有的操作步驟都是在輸入數(shù)組上進行的，不需要額外分配內(nèi)存，因此空間復(fù)雜度為O(1)。

不修改數(shù)組找出重復(fù)的數(shù)字（二分查找）

在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中任意一個重復(fù)的數(shù)字，但是不能修改輸入的數(shù)組。例如，如果輸入長度為8的數(shù)組{2,3,5,4,3,2,6,7}，那么對應(yīng)的輸出是重復(fù)的數(shù)字2或者3。

思路1：
由于不能修改輸入的數(shù)組，我們可以創(chuàng)建一個長度為n+1的輔助數(shù)組，然后逐一把原數(shù)組的每個數(shù)字復(fù)制到輔助數(shù)組。如果原數(shù)組中被復(fù)制的數(shù)字是m，則把它復(fù)制到輔助數(shù)組中下標(biāo)為m的位置。如果下標(biāo)為m的位置上已經(jīng)有數(shù)字了，則說明該數(shù)字重復(fù)了。由于使用了輔助空間，故該方案的空間復(fù)雜度是O(n)。

思路2：
由于思路1的空間復(fù)雜度是O(n)，因此我們需要想辦法避免使用輔助空間。我們可以想：如果數(shù)組中有重復(fù)的數(shù)，那么n+1個0~n范圍內(nèi)的數(shù)中，一定有幾個數(shù)的個數(shù)大于1。那么，我們可以利用這個思路解決該問題。

我們把從1~n的數(shù)字從中間的數(shù)字m分為兩部分，前面一半為1~m，后面一半為m+1~n。如果1~m的數(shù)字的數(shù)目等于m，則不能直接判斷這一半?yún)^(qū)間是否包含重復(fù)的數(shù)字，反之，如果大于m，那么這一半的區(qū)間一定包含重復(fù)的數(shù)字；如果小于m，另一半m+1~n的區(qū)間里一定包含重復(fù)的數(shù)字。接下來，我們可以繼續(xù)把包含重復(fù)的數(shù)字的區(qū)間一分為二，直到找到一個重復(fù)的數(shù)字。

由于如果1~m的數(shù)字的數(shù)目等于m，則不能直接判斷這一半?yún)^(qū)間是否包含重復(fù)的數(shù)字，我們可以逐步減少m，然后判斷1~m之間是否有重復(fù)的數(shù)，即，我們可以令m=m-1，然后再計算1~m的數(shù)字的數(shù)目是否等于m，如果等于m，再令m=m-1，如果大于m，則說明1~m的區(qū)間有重復(fù)的數(shù)，如果小于m，則說明m+1~n有重復(fù)的數(shù)，不斷重復(fù)此過程。

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的數(shù)組，那么函數(shù)countRange最多將被調(diào)用O(logn)次，每次需要O(n)的時間，因此總的時間復(fù)雜度是O(nlogn)。和前面提到的需要o(n)的輔助空間的算法比，這種算法相當(dāng)于以時間換空間。

二維數(shù)組中的查找

在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

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));