Created
January 6, 2018 18:32
-
-
Save jianminchen/11a0c1928992fd5eaf6d48b6a707d1f1 to your computer and use it in GitHub Desktop.
Matrix spiral copy - code review, readable variables, good idea to learn from the peer.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
/* | |
1. right (up = 0), down (right = n-1), left, up | |
O(m*n), space = O(1) | |
[[1]] | |
*/ | |
vector<int> spiralCopy( const vector<vector<int>>& inputMatrix ) | |
{ | |
// your code goes here | |
if(inputMatrix.size() == 0) | |
return {}; | |
int m = inputMatrix.size(); | |
int n = inputMatrix[0].size(); | |
int top = 0, right = n, left = -1, bottom = m; | |
vector<int> result; | |
int i = 0; | |
int j = 0; | |
int count = 0; | |
int turn = 0; // 0, 1, 2, 3 - each for direction right, down, left, up | |
while(count < m * n){ | |
if(turn == 0) | |
{ // Right | |
result.push_back(inputMatrix[i][j++]); | |
if(j == right){ | |
--j; | |
++i; | |
turn = 1; | |
right--; | |
} | |
count++; | |
} | |
else if(turn == 1){ // Down | |
result.push_back(inputMatrix[i++][j]); | |
count++; | |
if(i==bottom){ | |
--i; | |
--j; | |
turn = 2; | |
bottom--; | |
} | |
} | |
else if(turn == 2){ // Left | |
result.push_back(inputMatrix[i][j--]); | |
count++; | |
if(j==left){ | |
++j; | |
--i; | |
turn = 3; | |
left++; | |
} | |
} | |
else if(turn == 3){ // Up | |
result.push_back(inputMatrix[i--][j]); | |
count++; | |
if(i==top){ | |
++i; | |
++j; | |
turn = 0; | |
top++; | |
} | |
} | |
} | |
return result; | |
} | |
int main() { | |
vector<vector<int>> vec = { {}}; // two edges: empty, one element | |
vector<int> result = spiralCopy(vec); | |
for(auto a : result){ | |
cout<<a<<endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment