9度1384

タイトル1384:2 D配列での検索
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:7492
解決:1473
タイトルの説明:2 D配列では、各行が左から右に増加した順にソートされ、各列が上から下に増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.
入力:入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力される第1の動作の2つの整数mおよびn(1<=m,n<=1000):入力するマトリクスの行数および列数を表す.
入力された2行目には、検索する数値を表す整数t(1<=t<=1000000)が含まれます.
次のm行は、各行にn個の数があり、問題が与えるm行n列を表す行列(行列は、問題記述に示すように、各行が左から右に増加する順序で並べ替えられ、各列が上から下に増加する順序で並べ替えられる.
出力:各テストケースに対応し、
出力「Yes」は、2次元配列で数値tが見つかったことを表します.
出力「No」は、2次元配列に数字tが見つからないことを表す.
サンプル入力:3 3 3 5 1 2 3 4 5 6 7 8 9 3 3 1 2 3 4 5 6 7 9 3 3 12 3 4 5 6 7 9 10
サンプル出力:Yes No
 
問題解
久しぶりにOJでブラシをかけて、雑書を読みました.この行列<=1000で,時間制限は1 sであり,計算機演算速度の桁数は10^7/sであるため,テストデータが小さい場合は配列全体を直接インデックスすることができ,時間複雑度はO(n^2)である.次はプログラムですが、本当に過ぎたとは思いませんでした.

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=1000+10;
int array[MAXN][MAXN];


int main()
{
	int n,m,t;
	while(~scanf("%d%d",&n,&m))
	{
		scanf("%d",&t);
		int i,j;
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
				scanf("%d",&array[i][j]);
		}
		bool flag=false;
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				if(array[i][j]==t)
				{
					flag=true;
					break;
				}
			}
		}
		if(flag)
			printf("Yes
");
		else printf("No
");
	}
	return 0;
}

 
もちろん,上のアルゴリズムは極めて望ましくなく,問題条件を十分に利用していない:配列は各行が左から右に増加する順序で並べ替えられ,各列は上から下に増加する順序で並べ替えられる.考えてみると、線形アルゴリズムが現れた.まず2次元配列の4つの角のうちの1つから検索を開始し、右下角または左上角からのみ検索を開始し、配列の位置要素とtの関係を利用して行または列の増減を行うことができます.左上隅を選択し、現在の配列要素がtより小さい場合、その行は存在せず、その列の次の位置に移動します.tより大きい場合、列は存在せず、行の前の位置に移動します.検索する配列を変更するたびに、範囲は絶えず変化します.

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=1000+10;
int array[MAXN][MAXN];


int main()
{
	int n,m,t;
	while(~scanf("%d%d",&n,&m))
	{
		scanf("%d",&t);
		int i,j;
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
				scanf("%d",&array[i][j]);
		}
		
		int row=0,col=m-1;
		while(row<n&&col>=0)
		{
			if(array[row][col]>t)
				col--;
			else if(array[row][col]<t)
				row++;
			else break;
		}
		if(row<n&&col>=0)
			printf("Yes
");
		else printf("No
");
	}
	return 0;
}

    
このアルゴリズムの時間的複雑さはO(n)である.もちろん,問題の破綻と結びつけて配列データを入力する際に判断することができ,コードがより簡単になる.

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN=1000+10;
int array[MAXN][MAXN];


int main()
{
	int n,m,t;
	while(~scanf("%d%d",&n,&m))
	{
		scanf("%d",&t);
		int i,j;
		bool flag=false;
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				scanf("%d",&array[i][j]);
				if(array[i][j]==t)flag=true;
			}
		}
		if(flag)
			printf("Yes
");
		else printf("No
");
	}
	return 0;
}

   
能力が限られていて、間違いや不足があるのは避けられないので、斧正を望んでいます.