The title

Two ordered arrays of length N, find the NTH, N+1 largest number

Idea 1: Double Pointers, O(N) complexity

If the current array A points to is smaller than the current array B points to, then A moves to the right and nums is incremented by one. If the number of numbers traversed at this time is equal to N, then the contents of array A pointed to by A pointer before Jiujiang move are sent to result. In other cases, the logic is reversed.

// Double pointer method
vector<int> GetMid_On(vector<int>& A, vector<int>& B, int N)
{
	int A_index = 0;
	int B_index = 0;
	int nums = 0;
	vector<int> result;
	while (A_index < N && B_index < N)
	{
		if (A[A_index] < B[B_index])
		{
			A_index++;
			nums++;
			if (nums == N)
			{
				result.push_back(A[A_index - 1]);
			}
			if (nums == N + 1)
			{
				result.push_back(A[A_index - 1]);
				returnresult; }}else 
		{
			B_index++;
			nums++;
			if (nums == N)
			{
				result.push_back(B[B_index - 1]);
			}
			if (nums == N + 1)
			{
				result.push_back(B[B_index - 1]);
				returnresult; }}// If two elements are the same
	}
	return result;
}



int main(a)
{
	vector<int> A = { 2.4.5.6.9 };
	vector<int> B = { 1.3.7.8.10 };
	vector<int> result = GetMid_On(A, B, 5);
	cout << result[0] << endl;
	cout << result[1] << endl;
	cout << "The end" << endl;
	return 0;
}
Copy the code

Idea 2: Iterative dichotomy

Initialize ab array start,end,mid; Then compare the size of each value to which mid refers. If A[a_mid] > B[b_mid], the NTH value is to the left of a_mid in A and to the right of b_mid in B, so we update a_end and b_start. b_start = b_mid; And, of course, if the length is even: a_end = a_mid; b_start = b_mid + 1; This is just a change to start, not the end value. For example: A = {2,4,6,8}; Hc-positie B = {1}; a_start = 0,a_end = 3 b_start = 0,b_end = 3 a_mid = b_mid = 3/2 =1; A[a_mid] > B[b_mid], and the length is even, so a_end = a_mid =1; B_start = b_mid +1 =2; So A is divided into: {2,4}; B is divided into {5,7}; a_start = 0,a_end = 1 b_start = 2,b_end = 3 a_mid = 1/2 =0; b_mid = (2+3)/2= 2; A[a_mid] < B[b_mid], and the length is even, so a_start = a_mid =1; B_end = b_mid =2; At this point a a_start = = a_end | | b_start = = b_end conditions, so you can judge the size of the two start value, smaller value N large number can be obtained:

// Iterative dichotomy to solve
vector<int> GetMid(vector<int>& A, vector<int>& B, int N)
{
	vector<int> result;
	int a_start = 0, a_end = N - 1;
	int b_start = 0, b_end = N - 1;
	// Initialize the middle position
	int a_mid = (a_start + a_end) / 2;
	int b_mid = (b_start + b_end) / 2;
	// The end of the loop condition: when the start and end of the array coincide, the existence of the NTH largest number
	while(a_start ! = a_end || b_start ! = b_end) {// Update the intermediate coordinates
		a_mid = (a_start + a_end) / 2;
		b_mid = (b_start + b_end) / 2;
		// If the median of A is the same as the median of B, both numbers are the NTH largest
		if (A[a_mid] == B[b_mid])
		{
			result.push_back(A[a_mid]);
			result.push_back(A[a_mid] > B[b_mid] ? B[b_mid]: A[a_mid]);
			return result;
		}
		// If the median of A is greater than the median of B, the NTH largest number is to the left of A and to the right of B, so we need to update a_end and b_start
		else if (A[a_mid] > B[b_mid])
		{
			// If the current length between a_start and a_end is even, then the middle value is mid
			if ((a_start + a_end) % 2= =0)
			{
				a_end = a_mid;
				b_start = b_mid;
			}
			else
			{
				a_end = a_mid;
				b_start = b_mid + 1; }}// If the median of A is less than the median of B, the NTH largest number is to the right of A and to the left of B, so we need to update a_start and b_end
		else
		{
			// If the current length between a_start and a_end is odd, then the middle value is mid
			if ((a_start + a_end) % 2= =0)
			{
				a_start = a_mid;
				b_end = b_mid;
			}
			// If the length between a_start and a_end is even, then mid+1
			else
			{
				a_start = a_mid + 1; b_end = b_mid; }}}// Determine the size of the two start values
	if (A[a_start] > B[b_start])
	{
		result.push_back(B[b_start]);
		if (b_start + 1 < N)
		{
			if (A[a_start] > B[b_start + 1])
				result.push_back(B[b_start + 1]);
			else
				result.push_back(A[a_start]);
		}
		else
			result.push_back(A[a_start]);
	}
	else
	{
		result.push_back(A[a_start]);
		if (a_start + 1 < N)
		{
			if (A[a_start + 1] <= B[b_start])
				result.push_back(A[a_start + 1]);
			else
				result.push_back(B[b_start]);
		}
		else
			result.push_back(B[b_start]);
	}
	return result;
}

int main(a)
{
	vector<int> A = { 2.4.5.6.9 };
	vector<int> B = { 2.4.5.6.9 };
	//vector
      
        B = {1,3,7,8,10};
      
	vector<int> result = GetMid(A, B, 5);
	for(int i = 0; i < result.size(a); i++) cout << result[i] << endl; cout <<"The end" << endl;
	return 0;
}
Copy the code

Idea 3: Recursive dichotomy

After writing the iterative method, the recursion puts a_start,a_end,b_start,b_end as arguments to the recursive function. The recursive function begins with the termination condition, referring to the iterative method. After the termination condition, write different assignments to a_start,a_end,b_start,b_end according to the size of the intermediate value, so as to achieve the purpose of dividing the array.

// Recursive dichotomy
vector<int> GetMid(vector<int>& A, vector<int>& B, int a_start,int a_end,int b_start,int b_end,int N)
{
	vector<int> result;
	// Initialize the middle position
	int a_mid = (a_start + a_end) / 2;
	int b_mid = (b_start + b_end) / 2;
	// If there is an answer
	if (A[a_mid] == B[b_mid])
	{
		result.push_back(A[a_mid]);
		result.push_back(A[a_mid] > B[b_mid] ? B[b_mid] : A[a_mid]);
		return result;
	}
	if (a_start == a_end || b_start == b_end)
	{
		// Determine the size of the two start values
		if (A[a_start] > B[b_start])
		{
			result.push_back(B[b_start]);
			if (b_start + 1 < N)
			{
				if (A[a_start] > B[b_start + 1])
					result.push_back(B[b_start + 1]);
				else
					result.push_back(A[a_start]);
			}
			else
				result.push_back(A[a_start]);
		}
		else
		{
			result.push_back(A[a_start]);
			if (a_start + 1 < N)
			{
				if (A[a_start + 1] <= B[b_start])
					result.push_back(A[a_start + 1]);
				else
					result.push_back(B[b_start]);
			}
			else
				result.push_back(B[b_start]);
		}
		return result;
	}
	// Update boundary values recursively
	if (A[a_mid] > B[b_mid])
	{
		// If the current length between a_start and a_end is even, then the middle value is mid
		if ((a_start + a_end) % 2= =0)
		{
			return GetMid(A, B, a_start, a_mid, b_mid, b_end, N);
		}
		else
		{
			return GetMid(A, B, a_start, a_mid, b_mid + 1, b_end, N); }}// If the median of A is less than the median of B, the NTH largest number is to the right of A and to the left of B, so we need to update a_start and b_end
	else
	{
		// If the current length between a_start and a_end is even, then the middle value is mid
		if ((a_start + a_end) % 2= =0)
		{
			return GetMid(A, B, a_mid, a_end, b_start, b_mid, N);
		}
		else
		{
			return GetMid(A, B, a_mid + 1, a_end, b_start, b_mid, N); }}}int main(a)
{
	vector<int> A = { 2.4.5.6.9 };
	//vector
      
        B = {2,4,5,6,9};
      
	int N = A.size(a); vector<int> B = { 1.3.7.8.10 };
	vector<int> result = GetMid(A, B, 0, N- 1.0,N- 1,N);
	for(int i = 0; i < result.size(a); i++) cout << result[i] << endl; cout <<"The end" << endl;
	return 0;
}
Copy the code