LeetCode #1030 MatrixCellsInDistanceOrder. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,그래프,Graph,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접, 데이터베이스, sql, query, 쿼리
Need to think bout enhancing performance
Runtime: 896 ms, faster than 5.22% of C++ online submissions for Matrix Cells in Distance Order.
Memory Usage: 23.9 MB, less than 57.50% of C++ online submissions for Matrix Cells in Distance Order.
LeetCode #1030
Q.
We are given a matrix with R rows and C columns has cells with integer coordinates (r, c), where 0 <= r < R and 0 <= c < C.
Additionally, we are given a cell in that matrix with coordinates (r0, c0).
Return the coordinates of all cells in the matrix, sorted by their distance from (r0, c0) from smallest distance to largest distance. Here, the distance between two cells (r1, c1) and (r2, c2) is the Manhattan distance, |r1 - r2| + |c1 - c2|. (You may return the answer in any order that satisfies this condition.)
정수 좌표를 셀로 가지고 있는 매트릭스가 주어지는데, R 은 rows 길이이고, C 는 cols 길이이다.
추가로, 매트릭스 안의 한 셀의 좌표 (r0, c0) 가 주어진다.
주어진 좌표 (r0, c0) 으로부터의 짧은 거리에서 긴거리 순서로 정렬된 매트릭스의 좌표 셀들을 반환하라.
이 때, 거리 구하는 것은 맨해튼 거리 |r1 - r2| + |c1 - c2| 공식을 따른다. 같은 거리에서 순서는 상관 없다.
Example 1:
Input: R = 1, C = 2, r0 = 0, c0 = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (r0, c0) to other cells are: [0,1]
Example 2:
Input: R = 2, C = 2, r0 = 0, c0 = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2] The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.
Example 3:
Input: R = 2, C = 3, r0 = 1, c0 = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (r0, c0) to other cells are: [0,1,1,2,2,3] There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].
Note:
- 1 <= R <= 100
- 1 <= C <= 100
- 0 <= r0 < R
- 0 <= c0 < C
Process
// Process
//1. Input rows, cols, r0, c0
//2. Iterate rows
// 2.1. Iterate cols
// 2.1.1. Calculate distance from (r0, c0)
// 2.1.2. Make coord vec
//3. Sort coord vec using calculated distance
//4. Return coordVec
// 처리과정
//1. 매트릭스길이 rows, cols / 지정좌표 r0, c0 입력받는다.
//2. rows 전체 반복한다.
// 2.1. cols 전체 반복한다.
// 2.1.1. r0, c0 로 부터의 거리를 구한다 (Manhatten method)
// 2.1.2. 좌표 벡터를 만들어둔다.
//3. 좌표벡터와 거리벡터를 거리벡터 기준으로 정렬한다.
//4. 좌표벡터 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
vector<vector<int>> allCellsDistOrder(int rows, int cols, int r0, int c0) {
vector<vector<int>> coordVec;
vector<float> distances;
// 2.
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
vector<int> coord;
distances.push_back(abs(i-r0) + abs(j-c0));
coord.push_back(i);
coord.push_back(j);
coordVec.push_back(coord);
}
}
// 3.
int indexMin;
float tempDistance;
vector<int> tempCoord;
for (int i = 0; i < distances.size() - 1; ++i) {
indexMin = i;
for (int j = i + 1; j < distances.size(); ++j) {
if (distances[j] < distances[indexMin]) {
indexMin = j;
}
}
tempDistance = distances[indexMin];
distances[indexMin] = distances[i];
distances[i] = tempDistance;
tempCoord = coordVec[indexMin];
coordVec[indexMin] = coordVec[i];
coordVec[i] = tempCoord;
}
return coordVec;
}
};
Something else you might like...?
