【迎战蓝桥】 算法·每日一题(详解+多解)– day1

🤞目录🤞 【大家好,我是爱干饭的猿,如果喜欢这篇文…

🤞目录🤞

【大家好,我是爱干饭的猿如果喜欢这篇文章,点个赞👍,关注一下吧,后续会一直分享题目与算法思路

🏀1. 二维数组中的查找

描述:

在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

[ [1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15] ]

给定 target = 7,返回 true。

给定 target = 3,返回 false。

数据范围:矩阵的长宽满足 0 \le n,m \le 5000≤n,m≤500 , 矩阵中的值满足 0 \le val \le 10^90≤val≤109
进阶:空间复杂度 O(1)O(1) ,时间复杂度 O(n+m)O(n+m)

解题思路:

🎈1. 方法一: 查找的本质是排除,使用可以用双重循环,如果arr[i][j] = target,则找到target,返回true,但是效率太低。

🎈2. 方法二:我们可以将target 与右上角值比较,达到每次排除一行或一列的效果

如果target 大于右上角值,则排除当前行;

如果target 小于右上角值,则排除当前列;

🎈方法二:代码如下:

🏀2. 旋转数组的最小数字

描述:

有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。

数据范围:1 \le n \le 100001≤n≤10000,数组中任意元素的值: 0 \le val \le 100000≤val≤10000

要求:空间复杂度:O(1)O(1) ,时间复杂度:O(logn)O(logn)

解题思路:

🎈1. 方法一:理论上,我们可以进行一次遍历即可,因为是非降序数组arr[i] < arr[i+1],所以当旋转后,遇到arr[i] > arr[i+1]时,该值(arr[i+1])就是最小值。

🎈2. 方法二:我们可以使用二分法进行定位,时间复杂度更低,定义 left 最左,right 最右,mid 中间

因为数组非降序,所以

如果arr[left] <= arr[mid],旋转数组就在mid右侧[mid…right],使left = mid;

如果arr[left] > arr[mid],旋转数组就在mid右侧[left…mid],使right = mid;

范围不断缩小,当left 与 right 相邻时,arr[right] 就是最小值。

🎈方法一:代码如下

🎈方法二:代码如下

🏀3. 调整数组顺序使奇数位于偶数前面

描述:

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。(进阶:保证奇偶位置不变)

示例:

[1, 2, 3, 4, 5]

输出:

[1, 3, 5, 2, 4]

解题思路:

🎈1. 方法一:使用二分法,定义 left 最左,right 最右,遍历数组,找 arr[left] 为偶数,arr[right] 为奇数,然后交换两值。

🎈2. 方法二:(进阶:保证奇偶位置不变):因为相对位置不能改变,不能用二分法,用直接插入法。遍历数组,当找到奇数时,将该奇数之前的偶数都后移一位,然后该奇数存入偶数前的位置。

🎈方法一:代码如下

🎈方法二:代码如下

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/2690.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部