杨氏数组
在一个二维数组中（每个一维数组的长度相同）,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数.
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
查找的过程:本质就是排除的过程
- 排除一个元素
- 排除一行/一列元素
方法1:遍历整个二维数组查找:时间复杂度O(N)
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int row = array.size();//行
int col = array[0].size();//列
//方法1:遍历查找 0(N)
for(int i =0;i<row;i++)
{
for(int j =0;j<col;j++)
{
//找到了,返回true
if(array[i][j] == target)
{
return true;
}
}
}
return false;
}
};
方法2:利用题目说的数组的规律:一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序
所以二维数组左上角的元素:是整行最大的,整列最小的 右下角的元素:是整行最小的,整列最大的
使用左下角/右上角元素都可以:查找一次可以去掉一行或者一列
假设用的是右上角的元素K1:如果要找的元素K比K1大,说明第一行行中不可能找到K,去掉第一行,跳到第二行.假设要找的元素比K1小,说明最后一列不可能找到K,去掉最后一列,跳到倒数第二列,以此不断去掉行/列,直到找到/找不到
例子:
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int row = array.size();//行
int col = array[0].size();//列
//从右上角开始找
//左上角元素: array[0][col-1]
int i = 0;
int j = col-1;
//防止越界
while(i<row && j>=0)
{
if(array[i][j]>target)
{
//target < array[i][j] 当前右上角的值>target -》排除当前列
j--;
}
else if(array[i][j]<target)
{
//target > array[i][j] 当前右上角的值<target -》排除当前行
i++;
}
else
{
return true;
}
}
//找不到
return false;
}
};
旋转数组
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1. NOTE:给出的所有元素都大于0,若数组大小为0,请返回0.
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
方法1:直接遍历数组找到最小值 ->多捞
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
//特殊情况判定-数组为空
if(rotateArray.empty())
{
return 0;
}
int n = rotateArray.size();
int min = rotateArray[0];//假设最小值为第一个元素
for(int i = 0;i<n;i++)
{
//更新min
min = min>rotateArray[i]?rotateArray[i]:min;
}
return min;
}
};
优化:
旋转之后有个特征,就是在遍历的时候,原始数组是非递减的,旋转之后,就有可能出现递减,第一次引起递减的数字,就是最小值
如:3 200 100 2 3 ->从100到2,就是递减,2就是数组的最小值
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
//特殊情况判定-数组为空
if(rotateArray.empty())
{
return 0;
}
int n = rotateArray.size();
int min = rotateArray[0];//防止是递增序列,则第一个数就是最小值
//由于是比较i和i+1的下标,所以i的范围:[0,n-2],防止越界
for(int i = 0;i<n-1;i++)
{
//第一次出现递减的情况,后面那个数字就是最小值
if(rotateArray[i]>rotateArray[i+1])
{
min = rotateArray[i+1];//下一个递减的位置就是min
break;
}
}
return min;
}
};
高效的方法:二分查找
定义首尾下标,因为是非递减数组旋转,所以旋转最后可以看做成两部分,前半部分整体非递减,后半部分整体非递减,前半部分的值整体大于后半部分的值 ->即要满足a[left] >= a[right]
我们假设如下定义,left指向最左侧,right指向最右侧,mid为二分之后的中间位置
left永远在原数组前半部分,right永远在原数组的后半部分,而范围会一直缩小
left mid right
a[mid]>=a[left] 说明mid处于非递减状态,目标最小值在右边 [ 试想两者相等 隐含条件a[left] >= a[right] ]
a[mid] <a[left] 说明mid处于递减状态,目标最小值在左侧
- a[mid] >= a[left],说明mid位置在原数组前半部分,进一步说明,目标最小值,在mid的右侧,让left=mid
- a[mid] < a[left], 说明mid位置在原数组后半部分,进一步说明,目标最小值,在mid的左侧,让right=mid
- 这个过程,会让[left, right]区间缩小**,当left和right相邻时,right指向的位置,就是最小元素的位置**
- 题目说的是非递减,也就意味着数据允许重复,因为有重复情况,就可能会有a[left] == a[mid] ==a[right]的情况,我们就无法判定数据在mid左侧还是右侧,需要线性遍历查找（注意,只要有两者不相等,我们就能判定应该如何缩小范围)
case1:
当a[left] = a[right] && a[left] == a[mid] 的时候,无法判定,只能遍历寻找min
注意:循环条件的书写
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
//特殊情况判定-数组为空
if(rotateArray.empty())
{
return 0;
}
int left = 0;
int right = rotateArray.size()-1;
int mid = 0;//如果不满足a[left]>=a[right]就不进入循环,返回第一个位置的值
while(rotateArray[left]>=rotateArray[right])
{
//当left和right相邻时,right位置的值就是数组最小值
if(right - left == 1)
{
mid = right;
break;
}
mid = left + (right - left)/2;
//注意:如果left,right,mid指向的值相同,就要线性查找
if(rotateArray[left] ==rotateArray[mid]
&&rotateArray[mid] == rotateArray[right])
{
int result = rotateArray[left];
//遍历[left,right]找min
//因为left,mid,right指向的值都是一样的
//所以也可以缩小遍历的范围:[left+1,right-1]
for(int i =left+1;i<right;i++)
{
//找最小值
result = result>rotateArray[i]?rotateArray[i]:result;
}
return result;
}
//试想两者相等隐含条件a[left] >= a[right]
if(rotateArray[mid] >= rotateArray[left])
{
left = mid;//目标值在右边
}
else
{
right = mid;//目标值在左边
}
}
return rotateArray[mid];//返回中间位置
}
};