【算法】剑指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)

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] 当前右上角的值
                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[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];//返回中间位置
    }
};

---