【算法】剑指offer-杨氏数组&&旋转数组

简介: 剑指offer-杨氏数组&&旋转数组

杨氏数组

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

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)

classSolution {

public:

   boolFind(inttarget, vector<vector<int>>array) {

       introw=array.size();//行

       intcol=array[0].size();//列

       //方法1:遍历查找 0(N)

       for(inti=0;i<row;i++)

       {

           for(intj=0;j<col;j++)

           {

               //找到了,返回true

               if(array[i][j] ==target)

               {

                   returntrue;

               }

           }

       }

       returnfalse;

   }

};

方法2:利用题目说的数组的规律:一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序

所以二维数组左上角的元素:是整行最大的,整列最小的  右下角的元素:是整行最小的,整列最大的

使用左下角/右上角元素都可以:查找一次可以去掉一行或者一列

假设用的是右上角的元素K1:如果要找的元素K比K1大,说明第一行行中不可能找到K,去掉第一行,跳到第二行.假设要找的元素比K1小,说明最后一列不可能找到K,去掉最后一列,跳到倒数第二列,以此不断去掉行/列,直到找到/找不到

例子:


classSolution {

public:

   boolFind(inttarget, vector<vector<int>>array) {

       introw=array.size();//行

       intcol=array[0].size();//列

       //从右上角开始找

       //左上角元素: array[0][col-1]

       inti=0;

       intj=col-1;

       //防止越界

       while(i<row&&j>=0)

       {

           if(array[i][j]>target)

           {

               //target < array[i][j] 当前右上角的值>target -》排除当前列

               j--;

           }

           elseif(array[i][j]<target)

           {

               //target > array[i][j] 当前右上角的值<target -》排除当前行

               i++;

           }

           else

           {

               returntrue;    

           }

       }

       //找不到

       returnfalse;

   }

};


旋转数组

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{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:直接遍历数组找到最小值 ->多捞

classSolution {

public:

   intminNumberInRotateArray(vector<int>rotateArray) {

       //特殊情况判定-数组为空

       if(rotateArray.empty())

       {

           return0;

       }

       intn=rotateArray.size();

       intmin=rotateArray[0];//假设最小值为第一个元素

       for(inti=0;i<n;i++)

       {

           //更新min

           min=min>rotateArray[i]?rotateArray[i]:min;

       }

       returnmin;

   }

};

优化:

旋转之后有个特征,就是在遍历的时候,原始数组是非递减的,旋转之后,就有可能出现递减,第一次引起递减的数字,就是最小值

如:3 200 100 2  3   ->从100到2,就是递减,2就是数组的最小值

classSolution {

public:

   intminNumberInRotateArray(vector<int>rotateArray) {

       //特殊情况判定-数组为空

       if(rotateArray.empty())

       {

           return0;

       }

       intn=rotateArray.size();

       intmin=rotateArray[0];//防止是递增序列,则第一个数就是最小值

       //由于是比较i和i+1的下标,所以i的范围:[0,n-2],防止越界

       for(inti=0;i<n-1;i++)

       {

           //第一次出现递减的情况,后面那个数字就是最小值

           if(rotateArray[i]>rotateArray[i+1])

           {

               min=rotateArray[i+1];//下一个递减的位置就是min

               break;

           }

       }

       returnmin;

   }

};


高效的方法:二分查找

定义首尾下标,因为是非递减数组旋转,所以旋转最后可以看做成两部分,前半部分整体非递减,后半部分整体非递减,前半部分的值整体大于后半部分的值 ->即要满足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


注意:循环条件的书写

classSolution {

public:

   intminNumberInRotateArray(vector<int>rotateArray) {

       //特殊情况判定-数组为空

       if(rotateArray.empty())

       {

           return0;

       }

       intleft=0;

       intright=rotateArray.size()-1;

       intmid=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])

           {

               intresult=rotateArray[left];

               //遍历[left,right]找min

               //因为left,mid,right指向的值都是一样的

               //所以也可以缩小遍历的范围:[left+1,right-1]

               for(inti=left+1;i<right;i++)

               {

                   //找最小值

                   result=result>rotateArray[i]?rotateArray[i]:result;

               }

               returnresult;

           }

           

           //试想两者相等隐含条件a[left] >= a[right]

           if(rotateArray[mid] >=rotateArray[left])

           {

               left=mid;//目标值在右边

           }

           else

           {

               right=mid;//目标值在左边

           }

       }

       returnrotateArray[mid];//返回中间位置

   }

};



相关文章
|
7天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
13 0
|
15天前
|
存储 SQL 算法
LeetCode第53题:最大子数组和【python 5种算法】
LeetCode第53题:最大子数组和【python 5种算法】
|
11天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
15天前
|
存储 机器学习/深度学习 算法
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
python 五种算法转置后翻转、层次旋转、递归分块、一次性旋转、环状替换 实现旋转图像【力扣题48】
|
19天前
|
算法 搜索推荐 Java
【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)
【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)
10 3
|
18天前
|
算法 计算机视觉
图像处理之图像快速旋转算法
图像处理之图像快速旋转算法
15 1
|
18天前
|
存储 算法
数据结构和算法学习记录——设计循环队列(数组实现循环队列)核心思路、题解过程、完整题解
数据结构和算法学习记录——设计循环队列(数组实现循环队列)核心思路、题解过程、完整题解
17 1
|
19天前
|
存储 算法 Java
【经典算法】 leetcode88.合并排序的数组(Java/C/Python3实现含注释说明,Easy)
【经典算法】 leetcode88.合并排序的数组(Java/C/Python3实现含注释说明,Easy)
12 1
|
19天前
|
存储 JavaScript 前端开发
【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
10 1
|
19天前
|
存储 算法
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离
算法训练,牛客.判断是不是平衡二叉树 牛客.最大子矩阵两个数组的交集牛客.数组中两个字符串的最小距离

热门文章

最新文章