• 基础算法:二分查找、异或运算


    作为一名程序员,不管是前端、后端、运维、测试、数据库、算法等等岗位,都是需要学习算法的,不仅能提升编程能力,还能提升思维逻辑、分析问题的能力,是IT职场必不可少的加薪技能。

    千里之行,始于足下,最好的学习时间是一年前,其次是现在。最近在网上学习左程云老师的算法基础,记录下我的学习结果。

    二分查找

    例子1:有序数组某元素最左位置

    给你一个n代表有一个长度为n的有序数组,然后给你一个k,你需要判断这个k是否在数组里面,如果存在就返回这个数从左往右第一次出现位置的下标,如果不存在输出-1。

    思路:数组有序,所以可以使用二分查找,期间如果找到k,则下标赋给临时变量index,直到切成唯一元素(l === r),比较后返回。最终index为输出值。

    1. let index = -1;
    2. find(0, N - 1, key, list);
    3. // 有序数组arr里,下标从 l 到 r 之间,二分查找最左的key。
    4. // 递归法:
    5. const find = (l, r, key, arr) => {
    6. if (l > r) return;
    7. if (l === r) {
    8. if (arr[l] === key) index = l;
    9. return;
    10. }
    11. // 二分
    12. let middle = l + ((r - l) >> 1);
    13. if (arr[middle] > key) {
    14. find(l, middle - 1, key, arr)
    15. }
    16. if (arr[middle] === key) {
    17. index = middle; // 找到临时最左,继续向左找
    18. find(l, middle - 1, key, arr)
    19. }
    20. if (arr[middle] < key) {
    21. find(middle + 1, r, key, arr)
    22. }
    23. }
    24. // 迭代法:
    25. const find = (l, r, key, arr) => {
    26. let middle = 0;
    27. while(l <= r) {
    28. middle = l + ((r-l) >> 1);
    29. if (arr[middle] === key) {
    30. index = middle;
    31. r = middle - 1;
    32. }
    33. if (arr[middle] > key) r = middle - 1;
    34. if (arr[middle] < key) l = miidle + 1;
    35. }
    36. }

    二分查找的时间复杂度为:O(logN)。空间复杂度为O(1)。

    而普通的从左向右遍历查询代码更简单,但是时间复杂度为:O(N),如下:

    1. const findKey = (l, r, key, arr) => {
    2. let index = -1;
    3. for (let i = l; i < r; i++) {
    4. if (arr[i] === key) { // 从左到右第一个
    5. index = i;
    6. break;
    7. }
    8. if (arr[i] > key) { // 大于则直接退出
    9. break;
    10. }
    11. }
    12. return index;
    13. }

    总结:当一个数组有序时候,查找某个元素的位置,或者查找某个元素最左(最右)的位置等等都可以使用二分查找,其时间复杂度为O(logN)。

    例子2:有序数组元素>=k的最左位置

    你需要输入一个n,一个数k,然后输入一个长度为n个大小的数组arr,然后你需要在arr上找满足>=K的最左位置,并且输出这个位置,如果不存在这个位置就输出-1。

    输入描述:

    1. 第一行输入一个n,k
    2. 第二行输入长度为n的数组arr

    思路:与例子1类似,改变一下判断条件即可。

    1. (function(){
    2. // 递归法
    3. const find = (l, r, k, arr)=>{
    4. if (l > r) return;
    5. if (l === r) {
    6. if (arr[l] >= k) index = l;
    7. return;
    8. }
    9. // 二分
    10. let middle = l + ((r - l) >> 1);
    11. if (arr[middle] >= k) {
    12. index = middle; // 找到临时最左,继续向左找
    13. find(l, middle - 1, k, arr)
    14. }
    15. if (arr[middle] < k) {
    16. find(middle + 1, r, k, arr)
    17. }
    18. }
    19. let a = readline().trim(),b = readline().trim();
    20. // 编码
    21. let N = Number(a.split(' ')[0]), k = Number(a.split(' ')[1]),
    22. list = b.split(' ').map((item) => Number(item));
    23. let index = -1;
    24. find(0, N-1, k, list);
    25. print(index)
    26. })();
    27. // 迭代法:
    28. const find = (l, r, key, arr) => {
    29. let middle = 0;
    30. while(l <= r) {
    31. middle = l + ((r-l) >> 1);
    32. if (arr[middle] >= key) {
    33. index = middle;
    34. r = middle - 1;
    35. }else{
    36. l = miidle + 1;
    37. }
    38. }
    39. }

    时间复杂度仍然为 O(logN)。

    例子3:获取任意一个局部最小元素位置

    定义局部最小的概念。arr长度为1时,arr[0]是局部最小。arr的长度为N(N>1)时,如果arr[0] < arr[1],那么arr[0]是局部最小;
    如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小;如果0<i<N-1,既有arr[i] < arr[i-1],又有arr[i] < arr[i + 1],那么arr[i]
    是局部最小。给定无序数组arr,已知arr中任意两个相邻的数都不相等,只需要返回arr中任意一个局部最小出现的位置即可,如果不存在这个位置就输出-1。

    1. (function(){
    2. // 迭代法
    3. const find = (l, r, arr)=>{
    4. if(r < 0) return -1
    5. if(r === 0) return 0
    6. if (arr[0]< arr[1]) return 0
    7. if (arr[r] < arr[r-1]) return r
    8. while(l <= r) {
    9. if(l === r) return l
    10. let mid = l + ((r-l) >> 1)
    11. if(arr[mid] < arr[mid-1]) {
    12. if(arr[mid] < arr[mid+1]){
    13. return mid
    14. }else {
    15. l = mid + 1
    16. }
    17. }else {
    18. r = mid - 1
    19. }
    20. }
    21. return -1
    22. }
    23. let N = Number(readline().trim()),b = readline().trim();
    24. // 编码
    25. let list = b.split(' ').map((item) => Number(item));
    26. print( find(0, N-1, list))
    27. })();

    异或运算

    异或运算性质:

    • 一个数异或0,则结果为这个数: a^0 = a。

    • 一个数异或它自己,则结果为0: a^a = 0。

    • 满足交换律和结合律:a^b^c == (a^b)^c == (a^c)^b。

    例子1:找出数组中奇数次出现的一个数

    一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到这一个数?

    1. // N为数组arr的长度
    2. const find = (N, arr) => {
    3. if(N < 1) return -1
    4. let res = 0
    5. for(let i = 0; i < N; i++) {
    6. res ^= arr[i]
    7. }
    8. return res
    9. }

    例子2:找出数组中奇数次出现的两个数

    给定一个数字arr,其中只有两个数字出现了奇数次,其它数字都出现了偶数次,按照从小到大顺序输出这两个数。

    思路:

    既然有两个奇数次出现的数,通过所有数字相异或可得出结果为(a^b),而且这两个数(a,b)必然至少有一位(二进制)是不同的,假设这位是第二位,a里为1,b里为0。==则数组中所有第二位为1的数相异或,结果必然为a;同理为0的相异或结果必为b。==

    关键就是两点:如何计算ab中第几位不同;如果获取数组中所有第某位(假设称为关键位)为1的数。

    1. // N为数组arr的长度
    2. const find = (N, arr) => {
    3. if(N < 2) return -1
    4. // 初始值,考虑到连续异或,所以设置为0
    5. let a = 0, b = 0, eor = 0
    6. for(let i = 0; i < N; i++) {
    7. // eor值为 a^b
    8. eor ^= arr[i]
    9. }
    10. // 获取ab中最右边位(关键位)为1的值,比如:0010
    11. let point = eor & (~eor + 1)
    12. for(let i = 0; i < N; i++) {
    13. // 如果这个数与 point 相与不为0,则这个数在关键位上为1,全部相异或则结果为a。
    14. if(arr[i] & point !== 0) {
    15. a ^= arr[i]
    16. }
    17. }
    18. b = point ^ a
    19. return a < b ? (a + ' ' + b) : (b + ' ' + a)
    20. }

    总结:

    两个关键点已经给出,关键点1:获取ab中最右边位(关键位)为1的值 的方式比较特殊:一个数 与上 这个数按位非再加一的数,就是这个数中最右边位为1,其他位为0的数。目的是方便提取关键点2。

  • 相关阅读:
    【SSO单点登录】ticket+token+redis 实现sso单点登录 && 防重放、防盗用、防篡改
    关于pycharm中句号变成点的问题
    Linux——匿名管道
    09 多线程与高并发 - CompletableFuture 源码解析
    安装zabbix-agent监控linux
    第四篇章:运行时数据区——共享空间
    数据的距离度量 一、欧式距离,曼哈顿距离,闵氏距离,切比雪夫距离,兰氏距离,马氏距离
    vue实现blob文档流下载文件
    社区系统项目复盘-7
    详解TCP网络协议栈的工作原理
  • 原文地址:https://blog.csdn.net/weixin_70437515/article/details/125455562