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

MycLambert 发布于2019-08-26 11:43 / 2719人阅读

摘要：如果下标为的位置上已经有数字了，则说明该数字重复了。二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

找出数组中重复的数字

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云服务器云服务器算法与数据结构数据结构与算法数据结构与算法教程数据结构与算法答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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