Guest User

Untitled

a guest
Jul 31st, 2021
651
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 KB | None | 0 0
  1. coordinate compression / index compression
  2. class Solution {
  3.     vector<int> compress(vector<int> a) {
  4.         vector<int> s = a;
  5.         sort(s.begin(), s.end());
  6.         s.resize( unique(s.begin(), s.end()) - s.begin() );
  7.         for(int i = 0; i < (int) a.size(); i++) {
  8.             a[i] = lower_bound(s.begin(), s.end(), a[i]) - a.begin();
  9.         }
  10.         return a;
  11.     }
  12. public:
  13.     vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
  14.        
  15.     }
  16. };
  17. sort all the values
  18. give the new id to arr[i][j] max id form row i or col j
  19.  
  20. . 2 .
  21. 1 ? .
  22. . 1 .
  23. 1 ? 3
  24. we need to consider both 4s
  25.  
  26. for every tuple (4, row, col) {
  27.     remember what it transforms to
  28. }
  29.  
  30.  
  31. X = max(in_row, in_col) + 1
  32.    
  33. for(i) {
  34.     for(j) {
  35.         tuples.push(arr[i][j], i, j);
  36.     }
  37. }
  38. sort(tuples) // O(N*M*log(N*M))
  39.    
  40.    
  41. O(N*M*log(...))
  42.    
  43.    
  44.    
  45. How to find a group of cells that should be all equal?
  46.    
  47. . . . .
  48. 7 . . .
  49. . . . .
  50. . . 7 7
  51. 7 . 7 .
  52. . . . .
  53.    
  54. for every row, store all occurrences of every value
  55.  
  56. map<int, vector<int>> where_in_row[HEIGHT], where_in_col[WIDTH];
  57. where_in_row[0] is a map describing row 0
  58. where_in_row[0][7] is a list of occurrences of value 7 in row 0
  59.  
  60. void dfs(int row, int col) { O(H*W*(H+W))
  61.     cc.push_back({row, col});
  62.     visited[row][col] = true;
  63.     int x = matrix[row][col];
  64.     vector<int> tmp = where_in_row[row][x];
  65.     where_in_row[row][x].clear();
  66.     for(int c2 : tmp) {
  67.         if not visited[row][c2]:
  68.             dfs(row, c2);
  69.     }
  70.    
  71.     tmp = ...col...;
  72.     ...col....clear()
  73.     for(int r2 : tmp) {
  74.         if not visited[r2][col]:
  75.             dfs(r2, col);
  76.     }
  77. }
  78.    
  79. int maxr[HEIGHT], maxc[WIDTH];
  80. for tuple (x, row, col) in sorted_tuples:
  81.     if not visited[row][col]:
  82.         // find CC with this cell
  83.         dfs(row, col)
  84.        
  85.         int new_value = 0;
  86.         for every cell in cc:
  87.             new_value = max(new_value, maxr[cell.first], maxc[cell.second])
  88.         for every cell in cc:
  89.             new_matrix[this cell] = new_value + 1;
  90.             maxr[cell.first] = max(..., new_value + 1)
  91.             maxc[...] = ...
  92.            
  93.    
  94.    
  95.  
  96. . . . 0
  97. . . . 2
  98. . . 3 3
  99. . . . 1
  100. 2 2 3
  101.  
  102.  
Advertisement
Add Comment
Please, Sign In to add comment