Write a program that examines a square matrix of integers with dimensions N x N. The first input line contains the matrix size N, and the rows of the matrix follow on successive input lines. All numbers in each row will be separated by a single space.
Determine how many matrix columns contain a permutation of the numbers 1, 2, ..., N (i.e. each of the numbers 1, 2, ..., N appears exactly once in the column). Write this number to the output.
Note: N may be as large as 1,000. If your program runs in O(N^3), it will be too slow to pass all the tests.
Example:
Input:
5
1 1 3 4 5
2 2 3 1 5
4 3 5 5 1
12 4 23 2 3
5 5 3 3 2
Output:
2
using System;
namespace Test
{
class Program
{
private static void GetMinMax(int[] arr, out int min, out int max)
{
min = max = arr[0];
int n = arr.Length;
for (var i = 0; i < n; i++)
{
if (min > arr[i]) min = arr[i];
if (max < arr[i]) max = arr[i];
}
}
private static bool isConsecutive(int[] arr)
{
var n = arr.Length;
int min, max;
GetMinMax(arr, out min, out max);
if (max - min + 1 == n)
{
int i,j;
for (i = 0; i < n; i++)
{
if (arr[i] < 0) j = -arr[i] - min; else j = arr[i] - min;
if (arr[j] > 0) arr[j] = -arr[j]; else return false;
}
return true;
}
return false;
}
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
var arr = new int[n][];
for (var i = 0; i < arr.Length; i++) arr[i] = new int[n];
for (int i = 0; i < n; i++)
{
var item = Console.ReadLine().Split(' ');
for (var j = 0; j < item.Length&&j<n; j++)
{
arr[j][i] = int.Parse(item[j]);
}
}
int count = 0;
for (var i = 0; i < n; i++) {
if (isConsecutive(arr[i])) count++;
}
Console.Write(count);
}
}
}
楼主可用自己的语言描述一下题目,再说一下编程的思路,这样大家才好帮助你
编写一个程序,检查尺寸为N x N的整数方阵。第一输入行包含矩阵大小N,矩阵的行位于连续的输入行上。 每行中的所有数字将用单个空格分隔。 确定有多少矩阵列包含数字1,2,...,N的排列(即数字1,2,...,N中的每一个在该列中仅出现一次)。 将此数字写入输出。
你好,我是问答小助手,非常抱歉,本次您提出的有问必答问题,超出我们目前的服务范围,暂时无法为您解答。
问答VIP目前服务范围为 :Python、Java、MySQL、Redis、网络、Linux、大数据、云计算、云原生、中间件、MongoDB、HBase、Zookeeper、Kafka等领域专业问题解答,为您提供解决问题的思路和指导。
不提供源码代写、项目文档代写、论文代写、安装包资源发送或安装指导等服务。
本次提问扣除的有问必答次数已为您补发到账户,我们后续会持续优化,扩大我们的服务范围,为您带来更好地服务。