Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- coordinate compression / index compression
- class Solution {
- vector<int> compress(vector<int> a) {
- vector<int> s = a;
- sort(s.begin(), s.end());
- s.resize( unique(s.begin(), s.end()) - s.begin() );
- for(int i = 0; i < (int) a.size(); i++) {
- a[i] = lower_bound(s.begin(), s.end(), a[i]) - a.begin();
- }
- return a;
- }
- public:
- vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
- }
- };
- sort all the values
- give the new id to arr[i][j] max id form row i or col j
- . 2 .
- 1 ? .
- . 1 .
- 1 ? 3
- we need to consider both 4s
- for every tuple (4, row, col) {
- remember what it transforms to
- }
- X = max(in_row, in_col) + 1
- for(i) {
- for(j) {
- tuples.push(arr[i][j], i, j);
- }
- }
- sort(tuples) // O(N*M*log(N*M))
- O(N*M*log(...))
- How to find a group of cells that should be all equal?
- . . . .
- 7 . . .
- . . . .
- . . 7 7
- 7 . 7 .
- . . . .
- for every row, store all occurrences of every value
- map<int, vector<int>> where_in_row[HEIGHT], where_in_col[WIDTH];
- where_in_row[0] is a map describing row 0
- where_in_row[0][7] is a list of occurrences of value 7 in row 0
- void dfs(int row, int col) { O(H*W*(H+W))
- cc.push_back({row, col});
- visited[row][col] = true;
- int x = matrix[row][col];
- vector<int> tmp = where_in_row[row][x];
- where_in_row[row][x].clear();
- for(int c2 : tmp) {
- if not visited[row][c2]:
- dfs(row, c2);
- }
- tmp = ...col...;
- ...col....clear()
- for(int r2 : tmp) {
- if not visited[r2][col]:
- dfs(r2, col);
- }
- }
- int maxr[HEIGHT], maxc[WIDTH];
- for tuple (x, row, col) in sorted_tuples:
- if not visited[row][col]:
- // find CC with this cell
- dfs(row, col)
- int new_value = 0;
- for every cell in cc:
- new_value = max(new_value, maxr[cell.first], maxc[cell.second])
- for every cell in cc:
- new_matrix[this cell] = new_value + 1;
- maxr[cell.first] = max(..., new_value + 1)
- maxc[...] = ...
- . . . 0
- . . . 2
- . . 3 3
- . . . 1
- 2 2 3
Advertisement
Add Comment
Please, Sign In to add comment