毎日1つのアルゴリズムシリーズ(5)(2つの配列が既知で、配列の中の要素は正と負があるが、いずれも小さいから大きいまで順番に並べられており、できるだけ小さい時間の複雑さを要求して1つのアルゴリズムを編纂して2つの配列の最大交差を求める)

昨日迅雷の面接に行ったばかりで、全体的には悪くないと思いますが、いくつかの穴埋め問題が間違っているのは濡れ衣を着せられています.普段いい加減な習慣を身につけているのも無理はありません.これからは必ずこのような欠点を直さなければなりません.全体的に問題の質は悪くありません.選択問題、穴埋め問題、簡単な答え問題、アルゴリズム問題があります.主にC++対象モデルの知識が多いです.まだいくつかのCOM関連の問題を試験して、アルゴリズムの問題についてはまだ簡単で、2つあります.1つ目はチェーンテーブルを反転して、もう1つは私のこの文章のテーマです.
 
テーマ:2つの配列が知られていて、配列の中の要素は正と負がありますが、すべて小さいから大きいまで順番に並べて、できるだけ小さい時間の複雑度で1つのアルゴリズムを編纂して2つの配列の最大の交差を求めることを要求します.次のようになります.
A[] = {-10,5, 6},
B[] = {2, 4, 5, 6, 12};
では交差は{5,6}
 
 
考え方一:
配列Aの各要素を順番に取り出し、取り出した各要素を配列Bで二分して検索し、見つからなかった場合は最後まで、見つかった場合はBの中のIndexがJ、Aの中のIndexがIであれば、I+1、J+1から2つの配列の要素を取り比較し、等しい場合は継続し、等しくなければ、では、Index Iから現在のIndex-1までが2つの配列の最大交差である.
 
コードは次のとおりです.

/*---------------------------------
Copyright by yuucyf. 2011.04.26
         
----------------------------------*/

#include "stdafx.h"
#include <assert.h>


int FindValue(const int *pB, int i32FirIdx, int i32EndIdx, int nValue)
{
	assert(NULL != pB);

	if (i32FirIdx > i32EndIdx)	return -1;

	int i32MidIdx = (i32FirIdx + i32EndIdx) / 2;
	if (pB[i32MidIdx] > nValue)
	{
		return FindValue(pB, i32FirIdx, i32MidIdx - 1, nValue);
	}
	else if (pB[i32MidIdx] < nValue)
	{
		return FindValue(pB, i32MidIdx + 1, i32EndIdx, nValue);
	}

	return i32MidIdx;
}


bool GetMaxSubArray(const int *pA, int nASize, const int *pB, int nBSize)
{
	assert(NULL != pA || NULL != pB);
	assert(0 <= nASize || 0 <= nBSize);

	int i32Idx = -1;
	int i32I = 0, i32J = 0;

	for (i32I = 0; i32I < nASize; i32I++)
	{
		if ((i32Idx = FindValue(pB, 0, nBSize - 1, pA[i32I])) != -1)
		{
			printf("Max sub array is : %d ", pA[i32I]);
			for (i32I++, i32J = i32Idx + 1; i32I < nASize && i32J < nBSize; i32I++, i32J++)
			{
				if (pA[i32I] == pB[i32J])
				{
					printf("%d ", pA[i32I]);
				}
			}

			return true;
		}
	}

	return false;
}


int _tmain(int argc, _TCHAR* argv[])
{
	int aryA[] = {-10, 5, 6};
	int aryB[] = {2, 4, 5, 6, 12};
	if (!GetMaxSubArray(aryA, sizeof(aryA)/sizeof(int), aryB, sizeof(aryB)/sizeof(int)))
	{
		printf("Not sub array!
");
	}

	return 0;
}

 
 
時間複雑度O(n*logn)
 
構想の2:直接stlの中のMapを借りて交点を求めて、集団の考えは:まず配列Aの中の元素をmapの中に挿入して、値をKeyとして、Valueは1に設定して、それから配列Bの中の元素をKeyとしてmapを調べて、もし探し当てて、しかも値が1ならばそれでは説明して交点に保存して、それから配列Bの次の元素は下へ引き続き探して、もし探し当てていないならば、では、変更された交差の長さを記録し、順次下に検索し、すべての交差を記録し、最後に遍歴した後、すべての交差を比較して最大の交差を見つければよい.