(78)删除有序数组中的重复项(79)排序矩阵查找

2024-04-14 08:04

本文主要是介绍(78)删除有序数组中的重复项(79)排序矩阵查找,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 每日一言
  • 2. 题目(78)删除有序数组中的重复项
    • 2.1 解题思路
    • 2.2 代码
  • 3. 题目(79)排序矩阵查找
    • 3.1 解题思路
    • 3.1.1 暴力查找
      • 暴力查找代码
    • 3.1.2 二分查找
      • 二分查找代码
    • 3.1.3 贪心
      • 贪心代码
  • 4. 结语


1. 每日一言

水晶帘动微风起,满架蔷薇一院香。 —高骈-


2. 题目(78)删除有序数组中的重复项

题目链接:删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。

  • 示例 1:
    输入:nums = [1,1,2]
    输出:2, nums = [1,2,_]
    解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

  • 示例 2:
    输入:nums = [0,0,1,1,1,2,2,3,3,4]
    输出:5, nums = [0,1,2,3,4]
    解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列


2.1 解题思路

使用双指针法

  1. 一个指针fast用于遍历数组元素,另一个指针slow用来指示当前有效的元素位置。
  2. 当fast指向的元素与slow指向的元素相同时,表示有重复元素,fast继续向前移动。
  3. 当fast指向的元素与slow指向的元素不同时,表示发现了新的不重复元素,将其复制到slow的下一个位置,然后同时移动fast和slow指针。
  4. 最终返回slow加1,即为去重后数组的长度。

2.2 代码

int removeDuplicates(int* nums, int numsSize) {int fast = 0;int slow = 0;while(fast < numsSize) {if(nums[fast] == nums[slow]) {fast++;} else {slow++;nums[slow] = nums[fast++];}}return slow+1;
}

3. 题目(79)排序矩阵查找

题目链接:排序矩阵查找

给定M×N矩阵,每一行、每一列都按升序排列,请编写代码找出某元素。

  • 示例:
    现有矩阵 matrix 如下:
    [
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
    ]
    给定 target = 5,返回 true。
    给定 target = 20,返回 false。

3.1 解题思路

3.1.1 暴力查找

通过两层嵌套的循环遍历整个矩阵,将目标值与矩阵中的每一个元素进行比较。如果找到了与目标值相等的元素,则返回true;否则遍历完整个矩阵后,返回false。

暴力查找代码

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){for(int i = 0; i < matrixSize; i++) {for(int j = 0; j < matrixColSize;j++) {if(matrix[i][j] == target) {return true;}}}return false;
}

3.1.2 二分查找

在每行进行二分查找,对每一行进行有序数组的二分查找。如果找到了与目标值相等的元素,则返回 true;否则在遍历完整个矩阵后,返回 false。

二分查找代码

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){for(int i = 0; i < matrixSize;i++) {int left = 0;int right = matrixColSize-1;while(left <= right) {int mid = left + (right - left)/2;if(matrix[i][mid] < target) {left = mid + 1;} else if(matrix[i][mid] > target) {right = mid - 1;} else {return true;}}}return false;
}

3.1.3 贪心

通过维护两个指针i和j,它们的初始位置分别为矩阵的右上角元素。然后根据当前元素与目标值的大小关系,逐步向左下角移动指针,直到找到目标值或者超出矩阵边界。

具体来说,如果当前元素大于目标值,则目标值不可能在当前元素所在的列,因此j减1;如果当前元素小于目标值,则目标值不可能在当前元素所在的行,因此i加1。通过这种方式,可以迅速缩小搜索范围,直到找到目标值或者遍历完整个矩阵。

贪心代码

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){int i = 0;int j = matrixColSize - 1;while(i < matrixSize && j >= 0) {if(matrix[i][j] > target) {--j;} else if(matrix[i][j] < target) {++i;} else {return true;}} return false;
}

4. 结语

请给自己些耐心,不要急于求成。
山外青山楼外楼,莫把百尺当尽头。
保持空杯心态加油努力吧!


都看到这里啦!真棒(*^▽^*)

可以给作者一个免费的赞赞吗,这将会鼓励我继续创作,谢谢大家

编程小白写作,如有纰漏或错误,欢迎指正


这篇关于(78)删除有序数组中的重复项(79)排序矩阵查找的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/902510

相关文章

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

SQL Server清除日志文件ERRORLOG和删除tempdb.mdf

《SQLServer清除日志文件ERRORLOG和删除tempdb.mdf》数据库再使用一段时间后,日志文件会增大,特别是在磁盘容量不足的情况下,更是需要缩减,以下为缩减方法:如果可以停止SQLSe... 目录缩减 ERRORLOG 文件(停止服务后)停止 SQL Server 服务:找到错误日志文件:删除

mysql删除无用用户的方法实现

《mysql删除无用用户的方法实现》本文主要介绍了mysql删除无用用户的方法实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 1、删除不用的账户(1) 查看当前已存在账户mysql> select user,host,pa

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.