网站备案信息如何注销,上海网站建设规范,杭州本地网站有哪些,正确的网址格式题目
两个有序数组长度为N#xff0c;找到第N、N1大的数
思路1#xff1a;双指针#xff0c;O(N)复杂度
简述思路#xff1a; 如果当前A指针指向的数组A的内容小于B指针指向的数组B的内容#xff0c;那么A指针往右移动#xff0c;然后nums(当前已经遍历过的数字个数)也…题目
两个有序数组长度为N找到第N、N1大的数
思路1双指针O(N)复杂度
简述思路 如果当前A指针指向的数组A的内容小于B指针指向的数组B的内容那么A指针往右移动然后nums(当前已经遍历过的数字个数)也加一。 如果此时已经遍历过的数字个数等于N那么九江移动之前的A指针指向的A数组的内容送入result。 其他情况以相反的逻辑进行。
//双指针法求解
vectorint GetMid_On(vectorint A, vectorint B, int N)
{int A_index 0;int B_index 0;int nums 0;vectorint 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]);return result;}}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]);return result;}}//如果两个元素相同}return result;
}int main()
{vectorint A { 2,4,5,6,9 };vectorint B { 1,3,7,8,10 };vectorint result GetMid_On(A, B, 5);cout result[0] endl;cout result[1] endl;cout 结束 endl;return 0;
}思路2迭代法二分
简述思路 先初始化ab数组的start,end,mid; 然后比较各自mid指向的值的大小。 如果A[a_mid] B[b_mid]说明第N大的值在A数组a_mid的左边在B数组b_mid的右边所以对a_end以及b_start做出更新: 长度为奇数的时候正好 a_end a_mid; b_start b_mid; 当然还要考虑到长度为偶数的情况 a_end a_mid; b_start b_mid 1; 这里只是对start进行修改对于end值不需要修改。可以举例 A {2,4,6,8}; B {1,3,5,7}; 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] ,并且长度为偶数所以 a_end a_mid 1 b_start b_mid 1 2 所以A被分割为{24} B被分割为{57} a_start 0,a_end 1 b_start 2,b_end 3 a_mid 1/2 0; b_mid (23)/2 2; A[a_mid] B[b_mid] ,并且长度为偶数所以 a_start a_mid 1 b_end b_mid 2 此时达成a_start a_end || b_start b_end条件所以可以判断两个start的值的大小取较小值可得到第N大的数
//迭代二分法去解
vectorint GetMid(vectorint A, vectorint B, int N)
{vectorint result;int a_start 0, a_end N - 1;int b_start 0, b_end N - 1;//初始化中间位置int a_mid (a_start a_end) / 2;int b_mid (b_start b_end) / 2;//循环结束条件当数组起始点与结束点重合的时候说明存在第N大的数while (a_start ! a_end || b_start ! b_end){//更新中间坐标a_mid (a_start a_end) / 2;b_mid (b_start b_end) / 2;//如果此时的A中位数与B的中位数相同说明两个都是第N大的数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;}//如果A的中位数B的中位数说明此时第N大的数在A的左边B的右边所以需要更新a_end以及b_startelse if (A[a_mid] B[b_mid]){//如果当前a_start-a_end之间的长度为偶数那么中间值就是midif ((a_start a_end) % 2 0){a_end a_mid;b_start b_mid;}else{a_end a_mid;b_start b_mid 1;}}//如果A的中位数B的中位数说明此时第N大的数在A的右边B的左边所以需要更新a_start以及b_endelse{//如果当前a_start-a_end之间的长度为奇数那么中间值就是midif ((a_start a_end) % 2 0){a_start a_mid;b_end b_mid;}//如果当前a_start-a_end之间的长度为偶数那么中间值就是mid1else{a_start a_mid 1;b_end b_mid;}}}//判断两个start的值的大小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]);elseresult.push_back(A[a_start]);}elseresult.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]);elseresult.push_back(B[b_start]);}elseresult.push_back(B[b_start]);}return result;
}int main()
{vectorint A { 2,4,5,6,9 };vectorint B { 2,4,5,6,9 };//vectorint B { 1,3,7,8,10 };vectorint result GetMid(A, B, 5);for(int i 0;i result.size();i)cout result[i] endl;cout 结束 endl;return 0;
}思路3递归法二分
写完迭代法之后递归将a_start,a_end,b_start,b_end作为递归函数的参数放入。递归函数的一开始写终止条件参考迭代法。 终止条件后面写根据中间值的大小对a_start,a_end,b_start,b_end进行不同赋值达到分割数组的目的。
//递归二分法求解
vectorint GetMid(vectorint A, vectorint B, int a_start,int a_end,int b_start,int b_end,int N)
{vectorint result;//初始化中间位置int a_mid (a_start a_end) / 2;int b_mid (b_start b_end) / 2;//如果有答案了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){//判断两个start的值的大小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]);elseresult.push_back(A[a_start]);}elseresult.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]);elseresult.push_back(B[b_start]);}elseresult.push_back(B[b_start]);}return result;}//递归更新边界值if (A[a_mid] B[b_mid]){//如果当前a_start-a_end之间的长度为偶数那么中间值就是midif ((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);}}//如果A的中位数B的中位数说明此时第N大的数在A的右边B的左边所以需要更新a_start以及b_endelse{//如果当前a_start-a_end之间的长度为偶数那么中间值就是midif ((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()
{vectorint A { 2,4,5,6,9 };//vectorint B { 2,4,5,6,9 };int N A.size();vectorint B { 1,3,7,8,10 };vectorint result GetMid(A, B, 0, N-1,0,N-1,N);for(int i 0;i result.size();i)cout result[i] endl;cout 结束 endl;return 0;
}
