1. Title:
Let X[0:n-1] and Y[0:n-1] be two arrays, and each array contains n ordered numbers. Try to design an O(logn) time divide and conquer algorithm to find the median of 2n numbers of X and y.
Algorithm idea:
In fact, we don't need to really merge the two arrays. We just need to find out where the median is.
The initial idea is to write a loop, and then judge whether it reaches the median position. When it arrives, it will return the result, but it will be troublesome to classify even and odd numbers here. When one of the arrays is traversed, the boundary judgment of the for loop will also be divided into several cases. Overall, although complexity does not affect, the code will look messy.
The first is how to combine odd and even numbers.
Len is used to represent the length of the merged array. If it is an odd number, we need to know the (len+1) / 2nd number. If it is traversed, we need to traverse int (len/2) + 1 times. If it is an even number, we need to know the number len/2 and len/2+1, and we also need to traverse len/2+1 times. So if we traverse, the odd and even numbers are len/2+1 times.
If the median is returned, odd numbers need the results of the last traversal, and even numbers need the results of the last and last traversal. So we use two variables left and right. Right saves the result of the current cycle and assigns the value of right to left before each cycle. In this way, in the last cycle, left will get the value of right, that is, the result of the last cycle, and then right will be updated to the last result.
How to write in the loop, when array a moves back and when array B moves back. Use aStart and bStart to represent the current position pointing to array A and array B respectively. If aStart is not at the end and the number at position a is less than the array at position B, it can be moved back. That is, aStart < m& & A [aStart] < B [bStart].
However, if there is no number in array B at the moment, continue to take the number B [bstart], it will cross the boundary, so judge whether bstart is greater than the length of the array, so that the following will not be executed (here, due to the short circuit characteristic, when the left discriminant is true, the right will not be executed automatically), and will not cause an error, so it will be increased to astart < m&& (bstart) > = n|a [aStart]<B[bStart])
Code implementation:
#include <iostream>
using namespace std;
double findMedianSortedArray(int A[], int n, int B[], int m){//Core idea: Simulation of a merging and sorting process
int len = n + m;
int left = -1, right = -1;//Right saves the result of the current cycle, and left will get the value of right, that is, the result of the previous cycle
int aStart = 0, bStart = 0;
for(int i = 0; i <= len / 2; i++){
left = right;
if((aStart < n) && (bStart >= m || A[aStart] < B[bStart])){
right = A[aStart++];
}else{
right = B[bStart++];
}
}
if((len & 1) == 0){//Do and operation by bit to see whether the last bit is 0 or 1, that is, whether len is even or odd
return (left + right) / 2.0 ;
}else{
return right;
}
}
int main(){
int nums;
cin >> nums;
while(nums--){
int n, m;
cin >> n >> m;
int num1[n], num2[m];
for(int i = 0; i < n; i++)
cin >> num1[i];
for(int j = 0; j < m; j++)
cin >> num2[j];
cout << findMedianSortedArray(num1, n, num2, m) << endl;
}
return 0;
}reference material: 1041 find the median of two positive arrays Jinzhou hungry BA's hungry blog - CSDN blog
2 Title:
There is a real number sequence 𝑎 1, 𝑎 2,..., 𝑎 𝑎 if 𝑖 is < 𝑗 and 𝑎 is > 𝑎 then (𝑎 is 𝑎, 𝑎 is 𝑗) constitutes an inverse pair. Please use the divide and conquer method to find the number of inverse pairs in the whole sequence and analyze the time complexity of the algorithm.
Algorithm idea:
First divide the array into two parts, then divide the left and right parts into two parts, until each group is divided into two elements, and then sort the two elements (here is the temporary array to be created with), first put the two elements into the temporary array after sorting, then put the temporary array into the array to be sorted, and then merge the sub arrays containing two elements after sorting (the meaning of merging here is to sort two subarrays as two elements. Of course, it can be seen here that it is the idea of recursion). Finally, many subarrays are merged into a large array, and the number of reverse pairs is counted in the process of merging.
Implementation code:
#include <iostream>
using namespace std;
int reversePairs(int a[], int left, int right, int temp[]);
int mergeAndCount(int a[], int left, int mid, int right, int temp[]);
int reversePairs(int a[], int n){
if(n < 2){//If there are only one or zero array elements, there is no reverse order pair
return 0;
}
int *copy = new int[n];
for(int i = 0; i < n; i++){//Copy an original array first
copy [i] = a[i];
}
int *temp = new int[n];//The auxiliary array temp is used to merge two ordered arrays
return reversePairs(copy, 0, n-1, temp);
}
int reversePairs(int a[], int left, int right, int temp[]){//Calculate the number of pairs in reverse order from the interval left right and sort them
if(left == right){//Recursive termination condition: when there is only one element in the array, there must be no reverse order pair
return 0;
}
int mid = left + (right - left) / 2;//It is not written as (left+right)/2 to prevent integer overflow
int leftPairs = reversePairs(a, left, mid, temp);//Number of left half reverse pairs
int rightPairs = reversePairs(a, mid+1, right, temp);//Number of reverse pairs in the right half
if(a[mid] <= a[mid+1]){//The left and right sections have been spliced in order and do not need to be merged
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(a, left, mid, right, temp);//Merge the left and right intervals
return leftPairs + rightPairs + crossPairs;
}
int mergeAndCount(int a[], int left, int mid, int right, int temp[]){
//Function execution premise: the elements in the left mid of the left interval are ordered, and the elements in the right mid+1-right interval are ordered
for(int i = left; i <= right; i++){
temp[i] = a[i];
}
int i = left;//Points to the first element of the left interval
int j = mid + 1;//The first element of the right interval
int count = 0;//Count the number of pairs in reverse order
for(int k = left; k <= right; k++){
if(i == mid + 1){//One of the elements in the left or right interval must be merged first, so we just need to copy the remaining elements into a
a[k] = temp[j];
j++;
}else if(j == right + 1){//The right section is merged first
a[k] = temp[i];
i++;
}else if(temp[i] <= temp[j]){//Merge the smaller one back to a
a[k] = temp[i];
i++;
}else{//Every time an element in the right interval merges back to a, the reverse order number is calculated
a[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
int main(){
int m;
cin >> m;
while(m--){
int n;
cin >> n;
int *a = new int[n];
int *temp = new int[n];
for(int i = 0; i < n; i++)
cin >> a[i];
cout << reversePairs(a, 0, n-1, temp) << endl;
delete []a;
delete []temp;
}
return 0;
}reference material: 1013 reverse order to Jinzhou hungry bully's hungry blog - CSDN blog
3. Title:
The largest subarray problem. An array A containing N integers (positive and negative), design an O(nlogn) algorithm to find and the largest non empty continuous subarray. Can you design an O(n) algorithm for this problem?
For example: [0, - 2, 3, 5, - 1, 2] should return 9;
[- 9, - 2, - 3, - 5, - 3] should return - 2.
Implementation code:
#include <iostream>
using namespace std;
int maxSubArray(int a[], int n){//If you want the largest subarray, the first number at the beginning of each time should be a positive number
int max = a[0];
int sum = a[0];//sum first points to the first number
for(int i = 1; i < n; i++){//Left endpoint of subarray
if(sum > 0){//As long as the sum is positive
sum += a[i];//Let the latter number be added up first, and then compare the size with max
}else{
sum = a[i];//If sum is negative, let sum point to the last number of the current subsequence as a new starting point
}
if(max < sum){
max = sum;
}
}
return max;
}
int main(){
int m;
cin >> m;
while(m--){
int n;
cin >> n;
int a[n+1];
for(int i = 0; i < n; i++)
cin >> a[i];
cout << maxSubArray(a, n) << endl;
}
return 0;
}reference material: 1014 largest subarray and Jinzhou hungry BA's hungry blog - CSDN blog
4 Title:
The sum of two elements is X. given a set s composed of n real numbers and another real number x, judge whether the sum of two elements in S is X. try to design a divide and conquer algorithm to solve the above problem, and analyze the time complexity of the algorithm.
Algorithm idea: simulate the merging sorting process + binary search.
Implementation code:
#include <iostream>
using namespace std;
const int maxn = 50001;
void Merge(int a[], int start, int mid, int end, int temp[]){
int i = start, j = mid + 1, k = 0;
while(i <= mid && j <= end){
temp[k++] = a[i] <=a[j] ? a[i++] : a[j++];
}
while(i <= mid){
temp[k++] = a[i++];
}
while(j <= end){
temp[k++] = a[j++];
}
int t = 0;
for(i = start; i <= end; i++){
a[i] = temp[t++];
}
}
void mergeSort(int a[], int start, int end, int temp[]){
if(start < end){//At least two elements in the array can be merged
int mid = start + (end - start) / 2;
mergeSort(a, start, mid, temp);
mergeSort(a, mid + 1, end, temp);
Merge(a, start, mid, end, temp);
}
}
bool findX(int a[], int len, int x){//First merge and sort the array, and then binary search to improve the search efficiency
if(len < 1)
return false;
int i = 0, j = len - 1;
while(i < j){//Binary search
if((a[i] + a[j]) == x){
return true;//End the while loop
}else if((a[i] + a[j]) < x){
i++;
}else{
j--;
}
}
return false;//At the end of the while loop, if no k is found, false is returned
}
int main(){
int m;
cin >> m;
while(m--){
int n, x;
cin >> n >> x;
int a[maxn], temp[maxn];
for(int i = 0; i < n; i++){
cin >> a[i];
}
mergeSort(a, 0, n-1, temp);
if(findX(a, n, x)) {
cout << "yes" << endl;
}else{
cout << "no" << endl;
}
}
return 0;
}reference material: 1016 two elements and Jinzhou hungry BA's hungry blog - CSDN blog
5 topic:
Define the left rotation operation of the string: move several characters in front of the string to the end of the string. For example, rotate the string abcdef left by 2 bits to get the string cdefab. Please implement the function of left rotation of the string. The complexity of time operation on the string with length n is O(n) and the auxiliary memory is O(1).
Algorithm idea:
(cubic inversion algorithm) assuming that the original array sequence is abcd1234, the array sequence to be transformed is required to be 1234 ABCD, that is, the loop is shifted to the right by 4 bits. After comparison, it is not difficult to see that the order of two paragraphs is unchanged: 1234 and ABCD. These two paragraphs can be regarded as two whole. The process of shifting K bits to the right is to exchange the two parts of the array. The transformation process is completed by the following steps:
1. Arrange abcd in reverse order: abcd 1234 → DCBA 1234;
2. Arrange 1234 in reverse order: dcba1234 → dcba4321;
3. All in reverse order: dcba4321 → 1234abcd.
Implementation code:
#include <iostream>
#include <string>
using namespace std;
void Reverse(char s[], int start, int end){
for(; start < end; start++, end--){
char temp = s[end];
s[end] = s[start];
s[start] = temp;
}
}
void RightShift(char s[], int n, int k){//n is the length of the string, shifted by k bits to the left
k %= n;//In case the number of bits shifted to the left is greater than the length of the string
Reverse(s, 0, k-1);
Reverse(s, k, n-1);
Reverse(s, 0, n-1);
}
int main(){
char s[] = "zxcvbn1234";
int k = 3;
RightShift(s, 10, k);
cout << "Shift left" << k << "String after bit s' = " << s;
return 0;
}
Operation results:
reference material: Array cyclic shift algorithm (left-hand string) [summary]_ jiaolongdy's column - CSDN blog