剑指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;}};