【算法】剑指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];//返回中间位置

   }

};



相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
3月前
|
算法 测试技术
【算法】二分算法——寻找旋转排序数组中的最小值
【算法】二分算法——寻找旋转排序数组中的最小值
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
28天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
26 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
28天前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
20 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
3月前
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
3月前
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
|
3月前
|
算法
【算法】模拟算法——外观数组(medium)
【算法】模拟算法——外观数组(medium)
|
3月前
|
算法
【算法】前缀和——除自身以外数组的乘积
【算法】前缀和——除自身以外数组的乘积
|
3月前
|
算法
【算法】前缀和——寻找数组的中心下标
【算法】前缀和——寻找数组的中心下标