(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

相关文章

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

使用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