spiral matrix visit Search a 2D Matrix

Recently I saw several problems related to matrix , I think it's interesting , The idea is also very representative , Record intentionally .

1.spiral matrix

Spiral traversal of the matrix , It is also a classic scene ,leetcode54 That's the question , Just give me a diagram .

The solution is : To set up left,right,up,down The four quantities represent the starting positions of the four edges , Then traverse along the four edges . Note the exit condition .

#include<iostream>
#include<vector>
using namespace std;

void run() {
    vector<vector<int>> nums = {
   {1,2,3,4}, {5,6,7,8}, {9,10,11,12}};
    int left=0, right=nums[0].size()-1, up=0, down=nums.size()-1;
    while(true) {
        for(int i=left; i<=right; i++) {
            cout<<nums[up][i]<<" ";
        }
        up++;
        if(up>down) break;
        for(int i=up; i<=down; i++) {
            cout<<nums[i][right]<<" ";
        }
        right--;
        if (right<left) break;
        for(int i=right; i>=left; i--) {
            cout<<nums[down][i]<<" ";
        }
        down--;
        if (down<up) break;
        for(int i=down; i>=up; i--) {
            cout<<nums[i][left]<<" ";
        }
        left++;
        if (left>right) break;
    }
}

int main(int argc, char const *argv[])
{
    run();
    return 0;
}

Check the code above ：
First from left->right Traversal , It is equivalent to traversing the upper edge . After the traversal is over , Yes up add 1 operation . And make a judgment , If at this time up>down, Indicates that the traversal has been completed , The loop ends .
The other three edge traversal logic is similar , Be careful when writing code .

2.Search a 2D Matrix

leetcode The first 74 The question is Search a 2D Matrix.
The title requires
Write an efficient algorithm to judge m x n Matrix , Is there a target value . The matrix has the following characteristics ：
The integers in each row are arranged in ascending order from left to right .
The first integer in each row is greater than the last integer in the previous row .

Requirements are efficient algorithms , At the same time, it is all kinds of order , It's easy to think of using binary search .
First thought ： Because the elements in each row are in order , Therefore, it is a natural idea to perform binary search on each row of data directly .
Perform binary search on a row of data , Complexity log(n), All in all m That's ok , So the total complexity is mlog(n).

The solution above , The ordered property of each row is applied , But it ignores the property of global order of matrix . So a better solution is to use the property of the overall order of the matrix , First, determine which row the data may be on , Then perform a binary search on the row .

#include<iostream>
#include<vector>
using namespace std;


pair<bool, int> binary_search_last_less(vector<vector<int>> &vec, int left, int right, int target) {
    int n = right;
    while(left <= right) {
        int mid = (left+right)/2;
        int num = vec[mid][0];
        if (num == target) {
            return make_pair(true, mid);
        } else if(num > target) {
            right = mid - 1;
        } else {
            if (mid == n || vec[mid+1][0] > target) return make_pair(false, mid);
            else left = mid + 1;
        }
    }
    return make_pair(false, -1);
}

int binary_search(vector<int> &nums, int left, int right, int target) {
    while(left <= right) {
        int mid = (left+right)/2;
        if (nums[mid] < target) {
            left = mid+1;
        } else if (nums[mid] > target) {
            right = mid-1;
        } else {
            return mid;
        }
    }
    return -1;
}

pair<int, int> search(vector<vector<int>> &vec, int target) {
    int m=vec.size(), n=vec[0].size();
    pair<bool, int> ret = binary_search_last_less(vec, 0, m-1, target);
    if (ret.first) return make_pair(ret.second, 0);
    int row = ret.second;
    if (row == -1) return make_pair(-1, -1);
    int column = binary_search(vec[row], 0, n-1, target);
    if (column == -1) return make_pair(-1, -1);
    else return make_pair(row, column);
}

int main(int argc, char const *argv[])
{
    vector<vector<int>> vec = {
   {1,3,5,7}, {10,11,16,20}, {23,30,24,60}};
    int target = 60;
    pair<int, int> result = search(vec, target);
    cout<<result.first<<" "<<result.second<<endl;
    return 0;
}

The code above looks like it's very long , In fact, the logic is quite clear .

binary_search_last_less Method , The search object is the first column of the matrix , Judge target Whether it is in the same column . If not in the first column , be target Must be at the last less than target That line ( If it exists ).

binary_search Is the classic binary search , Find object is target The line that might be on .

search The method is to judge various situations .
1. If target In the first column , Direct return
2.target Not in the first column , And the last one is less than target The first column of the element row index is -1, Explain that all data of the matrix are greater than target, Return results .
3. The last one is less than target The first column element row index of is not -1, Then perform a binary search on the row , Last result returned .

According to the above analysis , Is the idea particularly clear .

3.Search a 2D Matrix II

leetcode 240 The problem is another version of matrix search . The title is

Write an efficient algorithm to search m x n matrix matrix One of the goals in target . The matrix has the following characteristics ：

The elements of each row are arranged in ascending order from left to right .
The elements of each column are arranged in ascending order from top to bottom .

Because every line 、 Each column of elements is ordered , So we focus on each line / It is also possible to perform a binary search on each column .

Now we provide another way to solve .
If we traverse from the top right corner , The number to the left becomes smaller , Down, the number gets bigger , It's a bit similar to binary search tree

So we can take target Compare with the current value .

If target The value of is greater than the current value , Then go down .
If target The value of is less than the current value , Then go left .
If it's equal, return .
Go down , It is equal to discarding the current row ; turn left , Equal to discarding the current column , This has played a role in accelerating .

#include<iostream>
#include<vector>
using namespace std;

pair<int, int> search(vector<vector<int>> &vec, int target) {
    int m = vec.size(), n = vec[0].size();
    int x = 0, y = n-1;
    while(x <= m-1 && y >= 0) {
        if (vec[x][y] > target) {
            y--;
        } else if (vec[x][y] < target) {
            x++;
        } else {
            return make_pair(x, y);
        }
    }
    return make_pair(-1, -1);
}

void run() {
    vector<vector<int>> vec = {
   {1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
    int target = 20;
    auto result = search(vec, target);
    cout<<result.first<<" "<<result.second<<endl;
}

int main(int argc, char const *argv[])
{
    run();
    return 0;
}