【OJ】关于顺序表的经典题目(移除数组中指定元素的值、数组去重、合并两个有序的数组)

news/2024/11/13 5:31:18/

文章目录

  • 前言
  • 题目1:移除数组中指定的元素
    • 题目描述
    • 解题思路
      • 方法1 :暴力法
      • 方法2:双指针法
  • 题目2:数组去重
    • 题目描述
    • 解题思路
      • 双指针法
  • 题目3:合并两个有序的数组
    • 题目描述
    • 解题思路
      • 方法1:暴力破解法
      • 方法2:从后往前

前言

通过有关顺序表的知识讲解,相信大家或多或少都对顺序表有一定的了解。

那么在本文中,我们将会给出几道有关于顺序表(个人觉得于数组的相关性较大)经典的代码练习题,并且总结一些做题的经验,呈现给大家。
哈哈哈

题目1:移除数组中指定的元素

题目链接:移除元素 - LeetCode

题目描述

题目表述
示例

解题思路

方法1 :暴力法

相信很多人看到这道题的时候,会不自觉的这样想:我先遍历题目所给的数组,在遍历的过程中,将每个数组中的每个元素与题目所给的那个val进行比较。如果不相等的话,我就把那个元素赋值到我新建的数组中。

由于这个想法比较简单,这里我就不画图进行讲解了。

实现的代码如下:

//方法1:暴力法
#include<stdlib.h>
int removeElement(int* nums, int numsSize, int val) {//创建一个与题目所给数组一样大小的空间int* newnums = (int*)malloc(sizeof(int)*numsSize);if (newnums == NULL){perror("malloc fail");exit(1);}//开始进行删除数据int i = 0;int count = 0;while (i < numsSize){if (nums[i] != val){newnums[count++] = nums[i];}i++;}return count;
}

方法2:双指针法

图解

相信经过上面的描述,已经对双指针的用法有了初步的感觉了!如果还不会的话,不用担心,本文后面的题目仍会用到双指针法的。

实现的代码如下:

int removeElement(int* nums, int numsSize, int val) {//创建两个指针,但对于数组来说下表的移动也可以相当是指针的移动int src = 0, dst = 0;while (src < numsSize){if (nums[src] != val){nums[src++] = nums[dst++];}else{src++;}}return dst;}

题目2:数组去重

题目链接:数组去重 - LeetCode

题目描述

题目描述
案例演示

解题思路

这题的难点在于原地删除重复出现的元素,这个就意味着我们无法像上面那道题一样创建新数组去完成了。

那该怎么办呢?在仔细看一下条件,题目还说了数组的元素是非严格递增排列的。但是我们有前面移除数组元素题目做铺垫,这两道题的共性都在于删除元素。

那我们可以先用双指针法来尝试做一下这道题!

思路

解题过程

这里你会发现,指针src就像一个侦察兵,dst指针就像一个大本营。当指针src发现前面有埋伏时,它就会跟大本营说,前面有埋伏,你不要过来,让我看看还有哪个地方时没有敌人的埋伏的。当发现没有埋伏是,大本营就会根据src传递的信息记录下这个没有埋伏的地方!

看到这里,你会发现:噢,双指针法真的能解决这个问题。但是你再仔细思考一下,如果数组是乱序的话,还能不能这样做?
很显然是不能的,因为dst指针指向的位置一旦被赋值之后,dst指针就会往下挪动一个位置。那假如,src在数组很后面的位置找到了dst之前那个位置的值,那就没有办法检测到了。

双指针法

代码实现:

//双指针法
int removeDuplicates(int* nums, int numsSize)
{int dst = 0, src = 1;while (src < numsSize){if (nums[dst] == nums[src]){//说明,src位置的元素是重复出现的。我们就要记录下来这个位置。//做法就是,我们可以先不动dst位置,等到值不一样的时候,再移动并赋值。src++;}else{nums[++dst] = nums[src++];}}return dst+1;
}

可能有的读者这里会问,能不能在nums[dst] == nums[src]的时候,将dst和src指针都移动一个位置。答案是不能!
自己画图就可以理解这一点了。

也许看到这里,你会说双指针法很好用!确实,它非常的好用!


题目3:合并两个有序的数组

题目链接:合并两个有序的数组 - LeetCode

题目描述

题目描述
案例演示

解题思路

按照题目的要求给了我们两个非递减顺序排列的数组。目的就是让我们合并它们,并且合并之后数组是按照非递减顺序排列的。

那该怎么做呢?我们在没有思路时,可以先去看一下题目给出的一些案例。不过我相信有一个方法是大家都能想到的,这里我姑且叫它暴力破解法

方法1:暴力破解法

将两个有序数组合并成一个数组之后,在使用排序算法,将它变成有序的!没错这个方法的确可行。

代码实现如下:

//思路:先将两个数组合并之后,再排序
#include<stdlib.h>
int compare_int(const void* x, const void* y)
{return *((int*)x) - *((int*)y);
}void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {//申请一块地址空间,用于存放两个数组合并之后的数组int* nums = (int*)malloc(sizeof(int) * (m + n));if (nums == NULL){perror("malloc fail");exit(1);}int count = 0;for (int i = 0; i < m; i++){nums[count++] = nums1[i];}for (int i = 0; i < n; i++){nums[count++] = nums2[i];}//这里使用qsort函数进行排序qsort(nums,m+n,sizeof(int),compare_int);}

方法2:从后往前

前置
思路分析
过程
代码实现:

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int n1 = m -1 , n2 = n - 1;int end = n1 + n2 + 1;while(n1 >= 0 && n2 >= 0){if(nums1[n1] > nums2[n2]){nums1[end--] = nums1[n1--];}else{nums1[end--] = nums2[n2--];}}//循环退出之后,一定有个数组还未遍历完。//如果是nums1这个数组未遍历完,其实可以不用给它单独处理//因为,题目要求返回的是nums1//如果是nums2的话,那就要给它处理一下while(n2 >= 0){nums1[end--] = nums2[n2--];}//}}

到这里,我们习题就已经全部讲完了。

本文主要讲解了一种解题方法:双指针法,针对这个方法,我会还会再出题目的讲解的!

如果觉得本文讲的还不错的话,麻烦给偶点个赞吧!!!

哈哈哈


http://www.ppmy.cn/news/1524296.html

相关文章

多源BFS之矩阵距离

多源BFS 173. 矩阵距离 给定一个 N行 M列的 01矩阵 A&#xff0c;A[i][j]与 A[k][l]之间的曼哈顿距离定义为dist(i,j,k,l)|i−k||j−l| 输出一个 N行 M列的整数矩阵 B&#xff0c;其中&#xff1a; B[i][j]min1≤x≤N,1≤y≤M,A[x][y]1dist(i,j,x,y) 输入格式 第一行两个整数…

状压DP

状压DP 对于数据范围n<20的可以考虑状压DP 1.蒙德里安的梦想 题目描述 求把 N M NM NM 的棋盘分割成若干个 12 的的长方形&#xff0c;有多少种方案。 例如当$ N2&#xff0c;M4$ 时&#xff0c;共有 5 种方案。当 N 2 &#xff0c; M 3 N2&#xff0c;M3 N2&…

echarts 显示中国地图以及省份

这里使用echarts 4.9的版本显示中国地图&#xff0c;因为5.X的版本已经把地图模块分离出去了 可以从这里下载全国地图数据或各身份的数据 https://github.com/apache/echarts/tree/master/test/data/map 完整代码示例&#xff1a;中国地图 <!DOCTYPE html> <html&g…

全国各地身份证号开头6位数字及地区对照表

具体请前往&#xff1a;全国各地身份证号开头6位数字-省市县/区对照表

设计模式】Listener模式和Visitor模式的区别

文章目录 前言一、介绍Listener模式Visitor模式 二、代码实现2.1 Listener模式的Java实现2.2Listener模式的Go实现2.3Visitor模式的Java实现2.4Visitor模式的Go实现 三、总结 前言 在软件设计中&#xff0c;设计模式是解决特定问题的通用解决方案。Listener模式和Visitor模式是…

STL-stack/queue/deque(容器适配器)

目录 ​编辑 STL-stack 150. 逆波兰表达式求值 stack queue std::stack deque 性能测试 结构 STL-stack 栈的压入、弹出序列_牛客题霸_牛客网输入两个整数序列&#xff0c;第一个序列表示栈的压入顺序&#xff0c;请判断第二个序列是否可能为该栈的弹出顺序。假。题目…

信息安全国内外现状及技术要求示例(R155/R156)

国际政策、 法规的现状与趋势 鉴于对交通安全、社会安全甚至国家安全的重要影响&#xff0c;汽车网络安全、数据安全得到各相关国家和地区的高度重视&#xff0c;纷纷出台相关法规、标准。 信息安全法规 R155 法规适用范围覆盖了乘用车及商用车&#xff0c;适用于 M 类、N 类…

原生 input 中的 “type=file“ 上传文件

目标&#xff1a;实现文件上传功能 原型图&#xff1a; HTML部分&#xff1a; <div class"invoice-item"><div class"invoice-title">增值税专用发票</div><div class"invoice-box"><el-form-item label"标准…