(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

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip