數據結構與算法（數組） --javascript語言描述

MycLambert 發布于2019-08-26 11:43 / 2738人閱讀

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

找出數組中重復的數字

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

GPU云服務器云服務器算法與數據結構數據結構與算法數據結構與算法教程數據結構與算法答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/107439.html

數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

you_De 2019-08-16 15:26 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

gotham 2019-07-31 10:07 評論0 收藏0
JS數據結構與算法_排序和搜索算法

摘要：上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客，也是在面試中常常會被問到的一部分內容排序和搜索。上一篇：JS數據結構與算法_樹寫在前面這是《學習JavaScript數據結構與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...

姘擱『 2019-08-23 16:26 評論0 收藏0
數據結構與算法:常見排序算法

摘要：這是一個簡單的遞歸函數，你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。本章內容銜接上一章　數據結構與算法：二分查找內容提要兩種基本數據結構：數組常見操作: 數組降維、數組去重鏈表遞歸：遞歸是很多算法都使用的一種編程方法　　- 如何將問題分成基線條件和遞歸條件　　- 分而治之策略解決棘手問題 ...

wuyumin 2019-07-30 15:33 評論0 收藏0
數據結構與算法:常見排序算法

摘要：這是一個簡單的遞歸函數，你可以使用它來生成數列中指定序號的數值這個函數的問題在于它的執行效率非常低有太多值在遞歸調用中被重新計算。本章內容銜接上一章　數據結構與算法：二分查找內容提要兩種基本數據結構：數組常見操作: 數組降維、數組去重鏈表遞歸：遞歸是很多算法都使用的一種編程方法　　- 如何將問題分成基線條件和遞歸條件　　- 分而治之策略解決棘手問題 ...

Carson 2019-08-26 11:32 評論0 收藏0