剑指offer：搜索

JZ53 数字在升序数组中出现的次数
简单 通过率：33.35% 时间限制：1秒 空间限制：256M
知识点数组二分
描述
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)
示例1
输入：
[1,2,3,3,3,3,4,5],3
返回值：
4
示例2
输入：
[1,3,4,5],6
返回值：
0
第一种方法：k + 0.5 和 k - 0.5

class Solution {
public:int GetNumberOfK(vector<int> data ,int k) {return BinarySearch(data, k + 0.5) - BinarySearch(data, k - 0.5);}int BinarySearch(vector<int>& nums, float target) {int mid;int low = 0;int high = nums.size() - 1;while (low <= high) {mid = (low + high) / 2;if (nums[mid] < target) {low = mid + 1;} else if (nums[mid] > target) {high = mid - 1;}}return low;}
};

第二种方法：分别找到最左边的元素和最右边的元素

class Solution {
public:int GetNumberOfK(vector<int> data ,int k) {int len = data.size();if (len == 0) {return 0;}int left = search_left(data, k);int right = search_right(data, k);if (left == -1 && right == -1) {return 0;} else {return right - left + 1;} }int search_left(vector<int> arr, int k) {int mid;int low = 0;int high = arr.size() - 1;while (low < high) {mid = (low + high) / 2;if (arr[mid] == k) {high = mid;} else if (arr[mid] < k) {low = mid + 1;} else if (arr[mid] > k) {high = mid;}}if(arr[low] == k) {return low;} else {return -1;}   }int search_right(vector<int> arr, int k) {int mid;int low = 0;int high = arr.size() - 1;while (low < high) {mid = (low + high + 1) / 2;if (arr[mid] == k) {low = mid;} else if (arr[mid] < k) {low = mid;} else if (arr[mid] > k){high = mid - 1;}}if(arr[low] == k) {return low;} else {return -1;}}
};

JZ4 二维数组中的查找
中等 通过率：26.73% 时间限制：1秒 空间限制：256M
知识点数组
描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤500 ， 矩阵中的值满足 0≤val≤109
进阶：空间复杂度 O(1) ，时间复杂度 O(n+m)
示例1
输入：
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：
true
说明：
存在7，返回true
示例2
输入：
1,[[2]]
返回值：
false
示例3
输入：
3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：
false
说明：
不存在3，返回false

class Solution {
public:bool Find(int target, vector<vector<int> > array) {if ( array.empty() ) {return false;}// 规律：// 左下角的元素：大于它上边的元素，小于它右边的元素。// 右上角的元素：大于它左边的元素，小于它下边的元素。// 方法：从左下角元素开始，或者从右上角元素开始。// 这里采用从右上角开始的方法。int row = 0;int col = array[0].size() - 1;// array.size() 表示二维数组的行数（有几行，一维数组的数量）// array[0].size() 表示二维数组的列数（有几列，一维数组的长度）while ( row <= array.size() - 1 && col >= 0 ) {if ( array[row][col] == target ) {return true;} else if ( array[row][col] < target ) {row++;} else if ( array[row][col] > target ) {col--;}}return false;}
};

JZ11 旋转数组的最小数字
简单 通过率：34.35% 时间限制：1秒 空间限制：256M
知识点二分
描述
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000
要求：空间复杂度：O(1) ，时间复杂度：O(logn)
示例1
输入：
[3,4,5,1,2]
返回值：
1
示例2
输入：
[3,100,200,3]
返回值：
3

class Solution {
public:int minNumberInRotateArray(vector<int> rotateArray) {if ( 0 == rotateArray.size() ) {return 0;}//如果遍历一次，开始递增，然后突然下降，然后递增，这个突然下降的元素就是最小元素for ( int index = 0; index <= rotateArray.size()-2; index++ ) {if ( rotateArray[index] > rotateArray[index+1] ) {return rotateArray[index+1];}}//如果遍历一次都是递增，第一个元素就是最小元素return rotateArray[0];}
};

BM55 没有重复项数字的全排列
题目
题解(98)
讨论(161)
排行
面经new
中等 通过率：56.95% 时间限制：1秒 空间限制：256M
知识点
递归
描述
给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 0 < n \\le 60<n≤6
要求：空间复杂度 O(n!)O(n!) ，时间复杂度 O(n!）O(n!）
示例1
输入：
[1,2,3]
复制
返回值：
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
复制
示例2
输入：
[1]
复制
返回值：
[[1]]
复制

class Solution {
public:void recursion(vector<vector<int> > &res, vector<int> &num, int index){if (index == num.size() - 1) {res.push_back(num);} else {for(int i = index; i < num.size(); i++) { swap(num[i], num[index]);recursion(res, num, index + 1); swap(num[i], num[index]);}}}vector<vector<int> > permute(vector<int> &num) {//先按字典序排序sort(num.begin(), num.end()); vector<vector<int> > res;recursion(res, num, 0); return res;}
};

BM56 有重复项数字的全排列（这个题目是数组，和下一个题目字符串是相同的方法）

题目
题解(92)
讨论(158)
排行
面经new
中等 通过率：39.45% 时间限制：1秒 空间限制：256M
知识点
递归
描述
给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： 0 < n \\le 80<n≤8 ，数组中的值满足 -1 \\le val \\le 5−1≤val≤5
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)
示例1
输入：
[1,1,2]
复制
返回值：
[[1,1,2],[1,2,1],[2,1,1]]
复制
示例2
输入：
[0,1]
复制
返回值：
[[0,1],[1,0]]
复制

class Solution {
public:void recursion(vector<int> &num, vector<int> &used){//临时字符串满足条件放入字符串数组if(temp.size() == num.size()) {vec.push_back(temp);return;}//遍历所有元素，选取一个元素加入临时字符串tempfor(int i = 0; i < num.size(); ++i) {//如果该元素已经被加入临时字符串temp，继续遍历if(used[i] == 1) {continue;}//当前的元素str[i]和前一个元素str[i-1]相同，并且前一个元素str[i-1]已经用过，继续遍历if(i > 0 && num[i-1] == num[i] && 1 == used[i-1]) {continue;}//加入临时字符串temp.push_back(num[i]);//标记为使用过 used[i] = 1; //递归遍历recursion(num, used);//从临时字符串去除temp.pop_back();//标记为未使用used[i] = 0;}}vector<vector<int> > permuteUnique(vector<int>& num) {//先按字典序排序，使重复字符串相邻sort(num.begin(), num.end());//标记每个位置的字符是否被使用过//0表示未使用过，1表示使用过vector<int> used(num.size(), 0);//递归获取recursion(num, used);//返回结果return vec;}
private:vector<vector<int>> vec;vector<int> temp;
};

JZ38 字符串的排列（这个题目是字符串，和上一个题目数组是相同的方法）
中等 通过率：23.80% 时间限制：1秒 空间限制：256M
知识点字符串递归
描述
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n<10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。
示例1
输入：
“ab”
返回值：
[“ab”,“ba”]
说明：
返回[“ba”,“ab”]也是正确的
示例2
输入：
“aab”
返回值：
[“aab”,“aba”,“baa”]
示例3
输入：
“abc”
返回值：
[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]
示例4
输入：
“”
返回值：
[“”]
关联企业

class Solution {
public:void recursion(string &str, vector<int> &used){//临时字符串满足条件放入字符串数组if(temp.size() == str.length()) {vec.push_back(temp);return;}//遍历所有元素，选取一个元素加入临时字符串tempfor(int i = 0; i < str.length(); ++i) {//如果该元素已经被加入临时字符串temp，继续遍历if(used[i] == 1) {continue;}//当前的元素str[i]和前一个元素str[i-1]相同，并且前一个元素str[i-1]已经用过，继续遍历if(i > 0 && str[i-1] == str[i] && 1 == used[i-1]) {continue;}//加入临时字符串temp.push_back(str[i]);//标记为使用过 used[i] = 1; //递归遍历recursion(str, used);//从临时字符串去除temp.pop_back();//标记为未使用used[i] = 0;}}vector<string> Permutation(string str) {//先按字典序排序，使重复字符串相邻sort(str.begin(), str.end());//标记每个位置的字符是否被使用过//0表示未使用过，1表示使用过vector<int> used(str.size(), 0);//递归获取recursion(str, used);//返回结果return vec;}
private:vector<string> vec;string temp;
};

JZ44 数字序列中某一位的数字
简单 通过率：34.18% 时间限制：1秒 空间限制：256M
知识点模拟
描述
数字以 0123456789101112131415… 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。

数据范围： 0≤n≤109
示例1
输入：
0
返回值：
0

示例2
输入：
2
返回值：
2

示例3
输入：
10
返回值：
1

示例4
输入：
13
返回值：
1

class Solution {
public:int findNthDigit(int n) {//记录n是几位数int digit = 1;//记录当前区间的起始数字：1,10,100...long long start = 1;//记录当前区间的总共位数//第一个区间：    9 = 9 * 1 * 1；//第二个区间：  180 = 9 * 10 * 2; //第三个区间： 2700 = 9 * 100 * 3//公式：sum = 9 * start * digitlong long sum = 9; //将n定位在某个区间while(n > sum){n -= sum;start *= 10;digit++;//当前区间的总共位数sum = 9 * start * digit;}//定位n在哪个数字int num = start + (n - 1) / digit;//定位n在数字中的下标int index = (n - 1) % digit;//根据下标直接返回数字return to_string(num)[index] - '0';}
};