0


剑指offer<算法>---------------搜索算法

旋转数组的最小数字

题目来源:牛客网

1、问题描述

有一个长度为 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)

2、思路解析

思路一:全排列
将这一组数据从大到小排序,最后取出最小的数据,排序时可以调用库函数sort,还可以直接实现排序算法,只需最后将最小的数据返回即可
思路二:更新最小数据
定义一个变量赋值INT_MAX遍历数组,遇到比当前数据小的树时就更新数据,直到遍历完数组

代码实现

classSolution{public:intminNumberInRotateArray(vector<int> rotateArray){sort(rotateArray.begin(),rotateArray.end());return rotateArray[0]}};
class Solution {
public:intminNumberInRotateArray(vector<int> rotateArray){int min=INT32_MAX;for(int i=0;i<rotateArray.size();i++){if(min>rotateArray[i]){
                min=rotateArray[i];}}return min;}};

二维数组中的查找

题目来源:牛客网

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≤10
9

进阶:空间复杂度 O(1)O(1) ,时间复杂度 O(n+m)O(n+m)

2、思路解析

思路: 线性搜索
因为数组是从左到右是逐渐递增的从上到下也是逐渐递增的,所以从左下角开始搜索这是因为,每一个数字都比前边的和上边的数字大,搜索流程如下:
(1)从左下角开始搜索,当前数比sum小值往后移动直到遇到比sum大的数字
(2)遇到比sum大的数字,就往上移动因为上边的数据都比当前数据小
(3)如果找到当前数字和sum相等就直接返回true,循环结束没有找到就直接返回false。

3、代码实现

classSolution{public:boolFind(int target, vector<vector<int>> array){int row=array.size();int col=array[0].size()-1;int num=0;while(col>=0&&num<row){if(num<row&&target>array[num][col]){
                num++;}elseif(col>=0&&target<array[num][col]){
                col--;}elseif(col>=0&&col>=0&&array[num][col]==target){returntrue;}}returnfalse;}};

字符串的排列

题目来源:牛客网

1、问题描述

输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
在这里插入图片描述

数据范围:n < 10n<10
要求:空间复杂度 O(n!)O(n!),时间复杂度 O(n!)O(n!)
输入描述:
输入一个字符串,长度不超过10,字符只包括大小写字母。

2、思路解析

思路:DFS+回溯
开始判断字符串是否为NULL,为NULL直接返回NULL,后边不为NULL就交给为DFS函数实现。
(1)DFS函数每次从第一个字符开始,用标记矩阵记录使用过的字符,每一次都将字符插入到新的字符串中,同时更新标记矩阵。
(2)当新的字符换满足要求是就直接插入到结果数组中,或者字符串长度大于要求的长度。就会返回到上一层
(3)将前边的新增加到的字符删除掉同时更新标记矩阵

3、代码实现

classSolution{public:voidDFS(vector<string>&v,vector<int>&num,string &str,string &s,int cur,int idx){if(s.size()==idx){if(find(v.begin(),v.end(),s)==v.end()){
            string ss(s.begin(),s.end());
            
            v.push_back(ss);}return;}for(int i=0;i<str.size();i++){if(num[i]==0){
                 num[i]=1;
                 s+=str[i];DFS(v,num,str,s,cur,idx);
                s.pop_back();
                num[i]=0;}}}
    vector<string>Permutation(string str){
        vector<string> v;if(str.empty()){return v;}
        vector<int>num(str.size(),0);
        string s="";DFS(v,num,str,s,0,str.size());return v;}};

本文转载自: https://blog.csdn.net/qq_50408340/article/details/124882660
版权归原作者 自首的小偷 所有, 如有侵权,请联系我们删除。

“剑指offer<算法>---------------搜索算法”的评论:

还没有评论