Implement the class SubrectangleQueries
which receives a rows x cols
rectangle as a matrix of integers in the constructor and supports two methods:
1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)
- Updates all values with
newValue
in the subrectangle whose upper left coordinate is(row1,col1)
and bottom right coordinate is(row2,col2)
.
2. getValue(int row, int col)
- Returns the current value of the coordinate
(row,col)
from the rectangle.
Example 1:
Input ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"] [[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]] Output
[null,1,null,5,5,null,10,5]
Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]); // The initial rectangle (4×3) looks like: // 1 2 1 // 4 3 4 // 3 2 1 // 1 1 1 subrectangleQueries.getValue(0, 2); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 5 5 5 subrectangleQueries.getValue(0, 2); // return 5 subrectangleQueries.getValue(3, 1); // return 5 subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 10 10 10 subrectangleQueries.getValue(3, 1); // return 10 subrectangleQueries.getValue(0, 2); // return 5
Example 2:
Input ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"] [[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]] Output
[null,1,null,100,100,null,20]
Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]); subrectangleQueries.getValue(0, 0); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); // return 100 subrectangleQueries.getValue(2, 2); // return 100 subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20); subrectangleQueries.getValue(2, 2); // return 20
Constraints:
- There will be at most
500
operations considering both methods:updateSubrectangle
andgetValue
. 1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols
Solution 1: Simulation
Update the matrix values.
Time complexity:
Update: O(m*n), where m*n is the area of the sub-rectangle.
Query: O(1)
Space complexity: O(rows*cols)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class SubrectangleQueries { public: SubrectangleQueries(vector<vector<int>>& rectangle): m_(rectangle) {} void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) { for (int i = row1; i <= row2; ++i) for (int j = col1; j <= col2; ++j) m_[i][j] = newValue; } int getValue(int row, int col) { return m_[row][col]; } private: vector<vector<int>> m_; }; |
Solution 2: Geometry
For each update remember the region and value.
For each query, find the newest updates that covers the query point. If not found, return the original value in the matrix.
Time complexity:
Update: O(1)
Query: O(|U|), where |U| is the number of updates so far.
Space complexity: O(|U|)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class SubrectangleQueries { public: SubrectangleQueries(vector<vector<int>>& rectangle): m_(rectangle) {} void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) { updates_.push_front({row1, col1, row2, col2, newValue}); } int getValue(int row, int col) { for (const auto& u : updates_) if (row >= u[0] && row <= u[2] && col >= u[1] && col <= u[3]) return u[4]; return m_[row][col]; } private: const vector<vector<int>>& m_; deque<vector<int>> updates_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment