PAT-BASIC1050——螺旋矩阵

我的PAT-BASIC代码仓：https://github.com/617076674/PAT-BASIC

原题链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805275146436608

题目描述：

知识点：数组

思路一：用一个int型变量turns记录螺旋的圈数

首先根据输入的N确定矩阵的行数m和列数n。

关于如何螺旋遍历矩阵中的每一个元素，本思路和LeetCode054——螺旋矩阵中的思路一是一模一样的。但LeetCode054——螺旋矩阵中的思路一使用了一个m行n列的数组visited记录该位置元素是否已被访问过。本题就比较简单，我们在安放完矩阵中的每一个位置后，都需要判断的是index索引是否已经到达了数组中的最后一个位置。

时间复杂度和空间复杂度均是O(m * n)，其中m为矩阵的行数，n为矩阵的列数

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int compare(int num1, int num2);

int main() {
	int N;
	cin >> N;

	int m = N;
	int n = 1;

	for(int i = N - 1; i > 1; i--) {
		if(N % i == 0) {
			if(i - N / i >= 0 && i - N / i < m - n) {
				m = i;
				n = N / i;
			}
		}
	}

	vector<int> nums;
	int tempNum;

	for(int i = 0; i < N; i++) {
		cin >> tempNum;
		nums.push_back(tempNum);
	}

	sort(nums.begin(), nums.end(), compare);

	int result[m][n];

	int index = 0;

	int turns;
	int min = m;
	if(n < min){
		min = n;
	}
	if(min % 2 == 0){
		turns = min / 2 - 1;
	}else{
		turns = min / 2;
	}


	for(int k = 0; k <= turns; k++) {
		if(index < nums.size()){
		
		for(int i = k; i < n - k; i++) {
			result[k][i] = nums[index++];
			if(index >= nums.size()){
				break;
			}
		}
	}
	if(index < nums.size()){
		for(int i = 1 + k; i < m - k; i++) {
			result[i][n - 1 - k] = nums[index++];
			if(index >= nums.size()){
				break;
			}
		}
	}
	if(index < nums.size()){
		for(int i = n - 2 - k; i >= k; i--) {
			result[m - 1 - k][i] = nums[index++];
			if(index >= nums.size()){
				break;
			}
		}
	}
	if(index < nums.size()){
		for(int i = m - 2 - k; i > k; i--) {
			result[i][k] = nums[index++];
			if(index >= nums.size()){
				break;
			}
		}
	}
	}

	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			cout << result[i][j];
			if(j != n - 1) {
				cout << " ";
			}
		}
		cout << endl;
	}

	return 0;

}

int compare(int num1, int num2) {
	if(num1 >= num2) {
		return 1;
	} else {
		return 0;
	}
}

C++解题报告：

思路二：实时更新螺旋的四个边界left、right、top、bottom的值

首先根据输入的N确定矩阵的行数m和列数n。

关于如何向矩阵中填值，本思路和LeetCode054——螺旋矩阵中的思路二是一模一样的。

时间复杂度是O(m * n)。空间复杂度是O(1)。

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int compare(int num1, int num2);

int main() {
	int N;
	cin >> N;

	int m = N;
	int n = 1;

	for(int i = N - 1; i > 1; i--) {
		if(N % i == 0) {
			if(i - N / i >= 0 && i - N / i < m - n) {
				m = i;
				n = N / i;
			}
		}
	}

	vector<int> nums;
	int tempNum;

	for(int i = 0; i < N; i++) {
		cin >> tempNum;
		nums.push_back(tempNum);
	}

	sort(nums.begin(), nums.end(), compare);

	int result[m][n];
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			result[i][j] = 0;
		}
	}

	int index = 0;

	int top = 0;
	int bottom = m - 1;
	int left = 0;
	int right = n - 1;
	while(top <= bottom && left <= right){
		for(int i = left; i <= right; i++){
			result[top][i] = nums[index++];
		}
		top++;
		for(int i = top; i <= bottom; i++){
			result[i][right] = nums[index++];
		}
		right--;
		if(top <= bottom){
			for(int i = right; i >= left; i--){
				result[bottom][i] = nums[index++];
			}
			bottom--;
		}
		if(left <= right){
			for(int i = bottom; i >= top; i--){
				result[i][left] = nums[index++];
			}
			left++;
		}
	}
	
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			cout << result[i][j];
			if(j != n - 1) {
				cout << " ";
			}
		}
		cout << endl;
	}

	return 0;

}

int compare(int num1, int num2) {
	if(num1 >= num2) {
		return 1;
	} else {
		return 0;
	}
}

C++解题报告：