js算法初窥03(搜索及去重算法)

  前面我们了解了一些常用的排序算法,那么这篇文章我们来看看搜索算法的一些简单实现,我们先来介绍一个我们在实际工作中一定用到过的搜索算法——顺序搜索。

1、顺序搜索

其实顺序搜索十分简单,我们还是以第一篇文章写好的架子作为基础,在其中加入顺序搜索的方法:

//顺序搜索
this.sequentialSearch = function(item) {
    for(var i = 0; i < array.length; i++) {
        if(item === array[i]) {
            return i;
        };
    };
    return -1;
};

  我想这个代码没什么好说的。你一定能理解的十分透彻。那么下面我们来看看二分搜索。

2、二分搜索

  我们先来做一个简单的游戏。想象一个场景,我们在聚会,大约有7、8个人,这个时候有人提议我们来做个游戏吧。我来想一个1到100的数字,你们来猜数字是什么,我会依照我想的数字告诉你们猜测的数字是比我脑海中的数字大了还是小了。这就是二分搜索。

  与顺序搜索不同的是,二分搜索需要在搜索之前对要搜索的数组排序。我们来看下代码:

//二分搜索
this.binarySearch = function(item) {
    //先对数组进行快速排序
    this.quickSort();
    //low和high是边界指针,也就是item是高了还是低了的表示,mid是我们数组的中间索引变量,element则是对应的mid的元素
    var low = 0,high = array.length - 1,mid,element;
    //如果low小于等于high说明边界范围是合理的。
    while(low <= high) {
        //为mid和element变量赋值。
        mid = Math.floor((low + high) / 2);
        element = array[mid];
        // 如果中间值比我们要找的元素小,说明item在中间值的右侧,要注意我们的数组时排序过后的数组了。
        // 所以我们直接让等于0的low的值设置为mid+1,因为item>element,所以item必然在mid+1开始到high的区间范围内。
        // 下同。
        if(element < item) {
            low = mid + 1;
        } else if(element > item) {
            high = mid - 1;
        } else {
            return mid;
        };
    };
    return -1;
};

   其实二分搜索也并不难,看代码和注释就一定可以看懂的。感觉这篇内容实在是不太多,所以我决定再加入一些其他的内容吧。

3、去重

想必大家在面试中被问到过最多的问题就是排序和去重了吧。其实这个东西真的算是老生常谈了,但是却又有它存在的必要,其实说到底,去重更重要的是思想,而不是实现,就跟前面我们学过的那些数据结构和算法一样。

  下面我们就介绍一下去重的一些实现方法吧。

  1)set方法

    set是ES6新增的一种数据结构——集合,我在前面的有关集合的章节中也介绍过这种数据结构,集合是一种不允许重复的数据存在的数据结构,我们刚好可以利用这种特性来为数组去重。如果你还不了解set数据结构,可以去这里或者这里查看。

this.uniqueSetWay = function () {
    //array.form方法从类似数组或可迭代对象中创建一个新的数组实例
    var set = new Set(array);
    return Array.from(set);
};

//测试方法
var repeatArray = new ArrayList();
repeatArray.insert(1);
repeatArray.insert(1);
repeatArray.insert(3);
repeatArray.insert(3);
repeatArray.insert(5);
repeatArray.insert(7);
repeatArray.insert(7);
repeatArray.insert(9);
repeatArray.insert(9);
repeatArray.insert(8);
console.log(repeatArray.uniqueSetWay())

    要注意的是,我们这里仍旧使用了第一章所构建的数组类。

  2)双循环

//双循环
this.uniqueDoubleCycle = function () {
     var newArr = [];
    var len = array.length;
    var isRepeat;
  
    for(var i=0; i<len; i++) {  //第一次循环
        isRepeat = false;
        for(var j=i+1; j<len; j++) {  //第二次循环
            if(array[i] === array[j]){
                isRepeat = true;
                break;
            }
        }
        if(!isRepeat){
            newArr.push(array[i]);
        }
    }
    return newArr;
};

    这种方法使用了双重循环设置一个标记位,确定我们加入新数组的元素是否是重复的,代码很好理解,但是这是效率最低的实现方式。

  3)排序辅助去重

//利用排序算法来辅助判断
this.sortUnique = function () {
    var newArr = [];                  
     this.quickSort();
     //将原数组中的第一项放入新数组
      var newArr = [array[0]];
      // 我们来循环比较
      for(var i = 1; i < array.length; i++){
          //如果新数组中的最后一项与array[i]不想等,那么我们就把它加入新数组。
        if(array[i] !== newArr[newArr.length - 1]){
             newArr.push(array[i]);
            }
      }    
      return newArr;
};

    我们就简单的介绍这三种去重方法,其实有关于去重的实现有很多种,如果大家想要继续学习有关去重的一些内容,我这里给大家贴上几篇不错的文章。这里就不再多说。

    1、【 js 算法 】这么全的数组去重,你怕不怕?

    2、也谈JavaScript数组去重

    3、js数组去重

当然,有关数组去重的文章远不止这些,只是个人觉得这些内容还不错。本文中的代码也是借鉴于此。那么本文到这里也就差不多结束了,下面会和大家一起学习一下算法模式(递归、动态规划等)。

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

BZOJ 3670: [Noi2014]动物园【KMP变形 】

3670: [Noi2014]动物园 Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 2738  Solve...

3497
来自专栏编程

Python利器之迭代器

各位小伙伴们 大家周四愉快 今天要和大家探讨一个 Python的特色功能 也是Python有别于其他变成语言的 强大利器 迭代器 迭代这一个词可能有的小伙伴不理...

1917
来自专栏技术墨客

Java函数式开发——优雅的Optional空指针处理

    在Java江湖流传着这样一个传说:直到真正了解了空指针异常,才能算一名合格的Java开发人员。在我们逼格闪闪的java码字符生涯中,每天都会遇到各种nu...

1242
来自专栏进击的程序猿

进击算法:字符串匹配的 BM 算法

各种文本编辑器的 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。

2773
来自专栏斑斓

深入探索Scala的Option

程序员最深恶痛绝并力求避免的异常是NullPointerException,很不幸,我们往往又会忽略这个错误。不知是谁设计了Null这样的对象。我在文章《并非N...

3317
来自专栏函数式编程语言及工具

泛函编程(0)-什么是泛函编程

 什么是泛函编程(Functional Programming)?泛函编程就是用函数编写程序。这个回答太抽象,等于没说。 再说清楚一点:泛函编程就想砌积木一样把...

2078
来自专栏take time, save time

你所能用到的数据结构(八)

十一、不能被应用的理论不是好研究 前面介绍了堆栈的一些小小的理论模型,那么这样一个东西有什么作用呢?实际中不可能有那么一辆停在站台前方堵死的火车的,即使有,也...

2724
来自专栏owent

不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

631
来自专栏小詹同学

【记录帖】(No.001)从零打卡刷Leetcode

小詹一直觉得自己编程能力不强,想在网上刷题,又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢?欢迎和小詹一起定期刷leetcode,每周一周五更新...

1193
来自专栏数据结构与算法

Debug

复杂度证明 普通莫队时间复杂度为 证明: 当我们第i个询问转移的第i+1个询问时 如果第i个询问区间和第i+1个询问区间的左端点所在块的编号相同,那么左端...

35111

扫码关注云+社区

领取腾讯云代金券