八种常见顺序存储的算法

目录

1、线性枚举

1)问题描述

2)动图演示

3)示例说明

4)算法描述

5)源码详解

2、前缀和差分

1)问题描述

2)动图演示

3)样例分析

4)算法描述

5)源码详解

3、双指针

1)问题描述

2)动图演示

3)样例说明

4)算法描述

5)源码详解

4、二分枚举

1)问题描述​编辑

2)动图演示

3)样例说明

4)算法描述

5)源码详解

5、三分枚举

6、插入排序

1)问题描述

2)动图演示

3)样例说明

4)算法描述

5)源码详解

7、选择排序

1)问题描述

2)动图演示

3)样例说明

4)算法描述

5)源码详解

8、冒泡排序

1)问题描述

2)动图演示

3)样例说明

4)算法描述

5)源码详解


1、线性枚举

1)问题描述

2)动图演示

3)示例说明

  蓝色的数据代表的是数组数据,红色的数据代表当前枚举到的数据,这样就可以遍历所有的数据进行逻辑处理了。

4)算法描述

  遍历数组,进行条件判断,条件满足则执行逻辑。这里的条件就是 枚举到的数 是否小于 当前最小值,执行逻辑为 将 当前枚举到的数 赋值给 当前最小值

5)源码详解

int findMin(int* nums, int numsSize){int i, min = 100000;for(i = 0; i < numsSize; ++i) {     // (1)if(nums[i] < min) {             // (2)min = nums[i];}}return min;                         // (3)
}

  • (1) 遍历数组中所有的数;
  • (2) 如果 当前枚举到的数 比记录的变量min小,则将它赋值给min;否则,不做任何处理;
  • (3) 最后,min中存储的就是整个数组的最小值。

2、前缀和差分

1)问题描述

2)动图演示

3)样例分析

  如上图所示,只需要记录一个前缀和,然后就可以通过一次减法将区间的值计算出来。时间复杂度 O(1)。这种就是差分的思想。

原理:

sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l + 1] ...... a[r];

sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];

sum[r] - sum[l - 1] = a[l] + a[l + 1] + ......+ a[r];

4)算法描述

  第一个枚举,利用一个数组sum,存储前 i 个元素的和。
  第二个枚举,读入 m 组数据 l,r,对每组数据,通过 O(1) 获取答案,即
sum[r] - sum[l - 1]​。

5)源码详解

int sum[maxn];
int* prefixSum(int* nums, int numsSize, int m, int *l, int *r){int i;int *ret;for(i = 0; i < numsSize; ++i) {sum[i] = nums[i];if(i) sum[i] += sum[i-1];                 // (1) }ret = (int *) malloc( m * sizeof(int) );    // (2) for(i = 0; i < m; ++i) {int leftsum = l[i] == 0 ? 0 : sum[l[i]-1]; // (3) int rightsum = sum[r[i]];ret[i] = rightsum - leftsum;            // (4) }return ret;
}

  • (1) 计算前缀和;
  • (2) 需要返回的数组;
  • (3) 这里是为了防止数组下标越界;
  • (4) 核心 O(1) 的差分计算;

3、双指针

1)问题描述

2)动图演示

3)样例说明

  维护两个指针 i 和 j,区间 [i,j] 内的子串,应该时刻保持其中所有字符不重复,一旦发现重复字符,就需要自增 i(即执行 i = i + 1);否则,执行 j = j + 1,直到 j 不能再增加为止。
  过程中,记录合法情况下 j − i + 1 的最大值。

4)算法描述

  如上文所述,这种利用问题特性,通过两个指针,不断调整区间,从而求出问题最优解的算法就叫 “尺取法”,由于利用的是两个指针,所以又叫 “双指针” 算法。
  这里 “尺” 的含义,主要还是因为这类问题,最终要求解的都是连续的序列(子串),就好比一把尺子一样,故而得名。

算法描述如下:
  1)初始化 i = 0, j = i − 1,代表一开始 “尺子” 的长度为 0;
  2)增加 “尺子” 的长度,即 j = j + 1;
  3)判断当前这把 “尺子” [i,j] 是否满足题目给出的条件:
    3.a)如果不满足,则减小 “尺子” 长度,即 i = i + 1,回到 3);
    3.b)如果满足,记录最优解,回到 2);

  • 上面这段文字描述的比较官方,其实这个算法的核心,只有一句话:

    满足条件时,j++;不满足条件时,i++;

  • 如图所示,当区间 [i,j] 满足条件时,用蓝色表示,此时 j 自增;反之闪红,此时 i 自增。
    在这里插入图片描述

5)源码详解

int getmaxlen(int n, char *str, int& l, int& r) {int ans = 0, i = 0, j = -1, len;   // 1)memset(h, 0, sizeof(h));           // 2)while (j++ < n - 1) {              // 3)++h[ str[j] ];                 // 4)while (h[ str[j] ] > 1) {      // 5)--h[ str[i] ];++i;}len = j - i + 1;              if(len > ans)                  // 6)ans = len, l = i, r = j;}return ans;
}

  • 1)初始化 i = 0, j = -1,代表 s[i:j] 为一个空串,从空串开始枚举;
  • 2)需要维护一个哈希表,哈希表记录的是当前枚举的区间 s[i:j] 中每个字符的个数;
  • 3)只推进子串的右端点;
  • 4)在哈希表中记录字符的个数;
  • 5)当 h[ str[j] ] > 1满足时,代表出现了重复字符str[j],这时候左端点 i 推进,直到没有重复字符为止;
  • 6)记录当前最优解的长度 j - i + 1,更新;
  • 这个算法执行完毕,我们就可以得到最长不重复子串的长度为 ans,并且 i 和 j 这两个指针分别只自增 n 次,两者自增相互独立,是一个相加而非相乘的关系,所以这个算法的时间复杂度为 O(n) 。

4、二分枚举

1)问题描述

2)动图演示

3)样例说明

  需要找值为 5 的这个元素。
  黄色箭头代表都是左区间端点 l,红色箭头代表右区间端点 r。蓝色的数据为数组数据,绿色的数字代表的是数组下标,初始化 l = 0,r = 7,由于数组有序,则可以直接折半,令 mid =(l+r)/2=3,则 55 一定落入区间 [0,3],这时候令 r = 3,继续执行,直到 l > r 结束迭代。
  最后,当 mid = 2 时,找到数据 5。

4)算法描述

  a)令初始情况下,数组下标从 0 开始,且数组长度为 n,则定义一个区间,它的左端点是      l = 0,右端点是 r = n−1;
  b)生成一个区间中点 mid = (l+r)/2,并且判断 mid 对应的数组元素和给定的目标值的大小关系,主要有三种:
    b.1)目标值 等于 数组元素,直接返回 mid;
    b.2)目标值 大于 数组元素,则代表目标值应该出现在区间 [mid+1,r],迭代左区间端点:l=mid+1;
    b.3)目标值 小于 数组元素,则代表目标值应该出现在区间 [l,mid−1],迭代右区间端点:r=mid−1;
  c)如果这时候 l>r,则说明没有找到目标值,返回 −1;否则,回到 b)继续迭代。

5)源码详解

int search(int *nums, int numsSize, int target) {int l = 0, r = numsSize - 1;         // (1)while(l <= r) {                      // (2)int mid = (l + r) >> 1;          // (3)if(nums[mid] == target) {   return mid;                  // (4)}else if(target > nums[mid]) {l = mid + 1;                 // (5)}else if(target < nums[mid]) {r = mid - 1;                 // (6)}}return -1;                           // (7)
}

  • (1) 初始化区间左右端点;
  • (2) 一直迭代左右区间的端点,直到 左端点 大于 右端点 结束;
  • (3) >> 1等价于除 2,也就是这里mid代表的是lr的中点;
  • (4) nums[mid] == target表示正好找到了这个数,则直接返回下标mid
  • (5) target > nums[mid]表示target这个数在区间 [���+1,�][mid+1,r] 中,所以才有左区间赋值如下:l = mid + 1;
  • (6) target < nums[mid]表示target这个数在区间 [�,���−1][l,mid−1] 中,所以才有右区间赋值如下:r = mid - 1;
  • (7) 这一步呼应了 (2),表示这不到给定的数,直接返回 -1

5、三分枚举

  三分枚举 类似 二分枚举 的思想,也是将区间一下子砍掉一块基本完全不可能的块,从而减小算法的时间复杂度。只不过 二分枚举 解决的是 单调性 问题。而 三分枚举 解决的是 极值问题。

6、插入排序

1)问题描述

  给定一个 n 个元素的数组,数组下标从 0 开始,采用「 插入排序 」将数组按照 「升序」排列。

2)动图演示

3)样例说明

图示含义
蓝色柱形代表尚未排好序的数
绿色柱形代表正在执行 比较 和 移动 的数
橙色柱形代表已经排好序的数
红色柱形代表待执行插入的数

  我们看到,首先需要将 「第二个元素」 和 「第一个元素」 进行 「比较」,如果 前者 小于等于 后者,则将 后者 进行向后 「移动」前者 则执行插入;
  然后,进行第二轮「比较」,即 「第三个元素」 和 「第二个元素」、「第一个元素」 进行 「比较」, 直到 「前三个元素」 保持有序 。
  最后,经过一定轮次的「比较」 和 「移动」之后,一定可以保证所有元素都是 「升序」 排列的。

4)算法描述

整个算法的执行过程分以下几步:
  1) 循环迭代变量 i=1→n−1;
  2) 每次迭代,令 x=a[i],j=i−1,循环执行比较 x 和 a[j],如果产生 x≤a[j] 则执 行 a[j+1]=a[j]。然后执行j=j+1,继续执行 2);否则,跳出循环,回到 1)

5)源码详解

#include <stdio.h>int a[1010];void Input(int n, int *a) {for(int i = 0; i < n; ++i) {scanf("%d", &a[i]);}
}void Output(int n, int *a) {for(int i = 0; i < n; ++i) {if(i)printf(" ");printf("%d", a[i]);}puts("");
}void InsertSort(int n, int *a) {       // (1)int i, j; for(i = 1; i < n; ++i) {int x = a[i];                  // (2)for(j = i-1; j >= 0; --j) {    // (3)if(x <= a[j]) {            // (4)a[j+1] = a[j];         // (5)}elsebreak;                 // (6)}a[j+1] = x;                    // (7)}
} int main() {int n;while(scanf("%d", &n) != EOF) {Input(n, a);InsertSort(n, a);Output(n, a);}return 0;
} 

  • (1) void InsertSort(int n, int *a)为 插入排序 的实现,代表对a[]数组进行升序排序。
  • (2) 此时a[i]前面的 i-1个数都认为是排好序的,令x = a[i]
  • (3) 逆序的枚举所有的已经排好序的数;
  • (4) 如果枚举到的数a[j]比需要插入的数x大,则当前数往后挪一个位置;
  • (5) 执行挪位置的 �(1)O(1) 操作;
  • (6) 否则,跳出循环;
  • (7) 将x插入到合适位置;

7、选择排序

1)问题描述

  给定一个 �n 个元素的数组,数组下标从 00 开始,采用「 选择排序 」将数组按照 「升序」排列。

2)动图演示

3)样例说明

图示含义
蓝色柱形代表尚未排好序的数
绿色柱形代表正在执行 比较 的数
橙色柱形代表已经排好序的数
红色柱形有两种:1、记录最小元素 2、执行交换的元素

  我们发现,首先从 「第一个元素」 到 「最后一个元素」 中选择出一个 「最小的元素」,和 「第一个元素」 进行 「交换」
  然后,从 「第二个元素」 到 「最后一个元素」 中选择出一个 「最小的元素」,和 「第二个元素」 进行 「交换」
  最后,一定可以保证所有元素都是 「升序」 排列的。

4)算法描述

整个算法的执行过程分以下几步:
  1) 循环迭代变量 i=0→n−1;
  2) 每次迭代,令 min=i,j=i+1;
  3) 循环执行比较 a[j] 和 a[min],如果产生 a[j]<a[min] 则执行 min=j。执行 j=j+1,继续执行这一步,直到 j==n;
  4) 交换 a[i] 和 a[min],回到 1)

5)源码详解

#include <stdio.h>int a[1010];void Input(int n, int *a) {for(int i = 0; i < n; ++i) {scanf("%d", &a[i]);}
}void Output(int n, int *a) {for(int i = 0; i < n; ++i) {if(i)printf(" ");printf("%d", a[i]);}puts("");
}void Swap(int *a, int *b) {int tmp = *a;*a = *b;*b = tmp;
}void SelectionSort(int n, int *a) {  // (1)int i, j;for(i = 0; i < n - 1; ++i) {     // (2)int min = i;                 // (3)for(j = i+1; j < n; ++j) {   // (4)if(a[j] < a[min]) {min = j;             // (5)}}Swap(&a[i], &a[min]);        // (6) }
}int main() {int n;while(scanf("%d", &n) != EOF) {Input(n, a);SelectionSort(n, a);Output(n, a);}return 0;
} 

  • (1) void SelectionSort(int n, int *a)为选择排序的实现,代表对a[]数组进行升序排序。
  • (2) 从首元素个元素开始进行 n−1 次跌迭代。
  • (3) 首先,记录min代表当前第 i 轮迭代的最小元素的下标为 i。
  • (4) 然后,迭代枚举第 i+1 个元素到 最后的元素。
  • (5) 选择一个最小的元素,并且存储下标到 min中。
  • (6) 将 第 i 个元素 和 最小的元素 进行交换。

8、冒泡排序

1)问题描述

  给定一个 n 个元素的数组,数组下标从 0 开始,采用「 冒泡排序 」将数组按照 「升序」排列。

2)动图演示

3)样例说明

图示含义
蓝色柱形代表尚未排好序的数
绿色柱形代表正在执行比较的两个数
黄色柱形代表已经排好序的数

  我们看到,首先需要将 「第一个元素」 和 「第二个元素」 进行 「比较」,如果 前者 大于 后者,则进行 「交换」,然后再比较 「第二个元素」 和 「第三个元素」 ,以此类推,直到 「最大的那个元素」 被移动到 「最后的位置」 。
  然后,进行第二轮「比较」,直到 「次大的那个元素」 被移动到 「倒数第二的位置」 。
  最后,经过一定轮次的「比较」 和 「交换」之后,一定可以保证所有元素都是 「升序」 排列的。

4)算法描述

整个算法的执行过程分以下几步:
  1) 循环迭代变量 i=0→n−1;
  2) 每次迭代,令 j=i,循环执行比较 a[j] 和 a[j+1],如果产生 a[j]>a[j+1] 则交换两者的值。然后执行 j=j+1,这时候对 j 进行判断,如果 j≥n−1,则回到 1),否则继续执行 2)

5)源码详解

#include <stdio.h>int a[1010];void Input(int n, int *a) {for(int i = 0; i < n; ++i) {scanf("%d", &a[i]);}
}void Output(int n, int *a) {for(int i = 0; i < n; ++i) {if(i)printf(" ");printf("%d", a[i]);}puts("");
}void Swap(int *a, int *b) {int tmp = *a;*a = *b;*b = tmp;
}void BubbleSort(int n, int *a) {             // (1)bool swapped;int last = n;do {swapped = false;                     // (2)for(int i = 0; i < last - 1; ++i) {  // (3)if(a[i] > a[i+1]) {              // (4)Swap(&a[i], &a[i+1]);        // (5)swapped = true;              // (6)}}--last;}while (swapped);
} int main() {int n;while(scanf("%d", &n) != EOF) {Input(n, a);BubbleSort(n, a);Output(n, a);}return 0;
} 

  • (1) void BubbleSort(int n, int *a)为冒泡排序的实现,代表对a[]数组进行升序排序。
  • (2) swapped标记本轮迭代下来,是否有元素产生了交换。
  • (3) 每次冒泡的结果,会执行last的自减,所以待排序的元素会越来越少。
  • (4) 如果发现两个相邻元素产生逆序,则将它们进行交换。保证右边的元素一定不比左边的小。
  • (5) swap实现了元素的交换,这里需要用&转换成地址作为传参。
  • (6) 标记更新。一旦标记更新,则代表进行了交换,所以下次迭代必须继续。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2659990.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

攻防世界—no-strings-attached

# 攻防世界—no-strings-attached 介绍下——IDA内置脚本 shiftF12 收获——要一个一个大致看出代码在干嘛 先运行一遍 int __cdecl main(int argc, const char **argv, const char **envp) { setlocale(6, &locale); banner(); prompt_authentication(); authenti…

3D展2D数学原理

今年早些时候&#xff0c;我为 MAKE 杂志写了一篇教程&#xff0c;介绍如何制作视频游戏角色的毛绒动物。 该技术采用给定的角色 3D 模型及其纹理&#xff0c;并以编程方式生成缝纫图案。 虽然我已经编写了一般摘要并将源代码上传到 GitHub&#xff0c;但我在这里编写了对使这一…

vue多条数据渲染(带图片)

我在这用的为接口数据&#xff1a; 先调用接口获取需要的数据: 然后用&#xff1a;data绑定需要渲染的数据&#xff1b;&#xff08;记得包裹在<el-table>标签中&#xff09; 然后以此循环渲染数据&#xff1b;那怎么渲染出来图片呢&#xff1f; 在<el-table-column…

技术资讯:2023编程语言排行榜,出炉啦!

大家好&#xff0c;我是大澈&#xff01; 本文约2000字&#xff0c;整篇阅读大约需要4分钟。 感谢关注微信公众号&#xff1a;“程序员大澈”&#xff0c;免费领取"面试礼包"一份&#xff0c;然后免费加入问答群&#xff0c;从此让解决问题的你不再孤单&#xff01…

PMCW体制雷达系列文章(2) - PMCW雷达与CDM

说明 多发多收(MIMO)体制下关于天线阵列有两个核心的问题&#xff1a;一是天线阵列怎么排布&#xff1b;二是这么多发射通道如何发射。这两点不管对于FMCW雷达还是PMCW雷达都同样适用。关于雷达的发射问题&#xff0c;我之前写过一篇博文&#xff1a;车载毫米波雷达MIMO阵列的天…

python如何读取被压缩的图像

读取压缩的图像数据&#xff1a; PackBits 压缩介绍&#xff1a; CCITT T.3 压缩介绍&#xff1a; 读取压缩的图像数据&#xff1a; 在做图像处理的时候&#xff0c;平时都是使用 函数io.imread() 或者是 函数cv2.imread( ) 函数来读取图像数据&#xff0c;很少用PIL.Image…

什么是 NLP (自然语言处理)

NLP&#xff08;自然语言处理&#xff09;到底是做什么&#xff1f; NLP 的全称是 Natural Language Processing&#xff0c;翻译成中文称作&#xff1a;自然语言处理。它是计算机和人工智能的一个重要领域。顾名思义&#xff0c;该领域研究如何处理自然语言。 自然语言就是我…

java设计模式学习之【迭代器模式】

文章目录 引言迭代器模式简介定义与用途实现方式 使用场景优势与劣势在Spring框架中的应用迭代器示例代码地址 引言 想象一下&#xff0c;你在一个书店里浏览各种书籍。你可能会从头到尾查看每一本书&#xff0c;或者可能跳过一些不感兴趣的部分。在这个过程中&#xff0c;你实…

计算机操作系统(OS)——P1操作系统概述

1、操作系统的概念(定义) 1.1、什么是操作系统 __操作系统&#xff08;Operating System&#xff0c;OS&#xff09;&#xff1a;__是指控制和管理整个计算机系统的__硬件和软件__资源&#xff0c;并合理的组织调度计算机的工作和资源的分配&#xff1b;以__提供给用户和其它…

都2023年了还不了解?使用FileZilla搭建信息文件服务器(Windows7)

目录 前言&#xff1a; 一.FileZilla介绍 1.FileZilla介绍 2.FileZilla的优点以及不足 优点 不足 3.FileZilla应用场景 4.FileZilla的主要功能&#xff1a; 二.Windows7搭建FileZilla服务器&#xff0c;并且在本地访问 1.下载 2.FileZIlla安装 服务端安装 新建组 …

基于鸿蒙OS开发一个前端应用

创建JS工程&#xff1a;做鸿蒙应用开发到底学习些啥&#xff1f; 若首次打开DevEco Studio&#xff0c;请点击Create Project创建工程。如果已经打开了一个工程&#xff0c;请在菜单栏选择File > New > Create Project来创建一个新工程。选择HarmonyOS模板库&#xff0c…

uniapp开发移动端遇到的问题记录

1. 键盘弹起时页面整体上移问题 很常见但我解决过程中遇到了很多问题 我的键盘没有遮盖到输入框&#xff0c;但手机键盘弹起后&#xff0c;form部分会整体上移一点&#xff0c;并且底部的操作也会弹到键盘上方 网上写得很复杂&#xff0c;什么动态赋值高度balabala。看到有一…

12.18构建哈夫曼树(优先队列),图的存储方式,一些细节(auto,pair用法,结构体指针)

为结构体自身时&#xff0c;用.调用成员变量&#xff1b;为结构体指针时&#xff0c;用->调用成员变量 所以存在结构体数组时&#xff0c;调用数组元素里的成员变量&#xff0c;就是要用. 结构体自身只有在new时才会创建出来&#xff0c;而其指针可以随意创建 在用new时&…

基于Java+SpringBoot+vue实现图书借阅管理系统

基于JavaSpringBootvue实现图书借阅和销售商城一体化系统 &#x1f345; 作者主页 程序设计 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; 文章目录 基于JavaSpringBootvue实现图书借阅和销售商城一体化…

【Unity动画系统】Unity动画系统Animation详解,参数细节你是否弄清?

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…

【Web网站测试流程及方法】给你一个网站,你如何来做自动化测试的?

我想大多数开始进行web端页面测试的人&#xff0c;一开始会的都是在页面上点点点&#xff0c;然后一看到页面上有什么图片失效啊&#xff0c;页面遮挡就觉得是找到了大bug&#xff1b;一开始我也是这样&#xff0c;尽管我很谨慎&#xff0c;很仔细&#xff0c;把页面上的每一个…

hosts文件、DNS、删除浏览器域名安全策略、浏览器代理

文章目录 1. hosts文件2. DNS3. 删除浏览器域名安全策略4. 浏览器代理服务器 1. hosts文件 位置 C:\Windows\System32\drivers\etc\hosts 没有后缀名 内容 ip 一个空格 域名 定义 hosts就是系统的一个配置文件&#xff0c;主要配置ip和域名的映射关系&#xff0c;相当于是本地…

Ubuntu fcitx Install

ubuntu经常出现键盘失灵的问题 查询资料得知应该是Ibus框架的问题 于是需要安装fcitx框架和搜狗拼音 sudo apt update sudo apt install fcitx 设置fcitx开机自启动&#xff08;建议&#xff09; sudo cp /usr/share/applications/fcitx.desktop /etc/xdg/autostart/ 然后…

pyomo使用cplex求解,进行冲突校验

文章目录 求解参数设置模型保存模型冲突校验pyomo冲突校验cplex冲突校验docplex冲突校验 CPLEX 安装包下载 pyomo使用 cplex求解&#xff0c;进行冲突校验 求解参数设置 options {"timelimit" : 60*60, # 设置求解时间&#xff0c;超过设置时间&#xff0c;求解停…

EfficientNet

时间&#xff1a;2019 EfficicentNet网络简介 EfficientNet:Rethinking Model Scaling for Convolutional Neural Networkshttps://arxiv.org/abs/1905.11946,这篇论文是Google在2019年发表的文章。 EfficientNet这篇论文&#xff0c;作者同时关于输入分辨率&#xff0c;网络…