Given an integer array a containing n elements, find the maximum and minimum values.
The conventional approach is to traverse once and find the maximum and minimum values respectively, but what I am going to talk about here is the divide and conquer method (Divide and couquer). Divide the array into left and right parts and find the left half first. Find the maximum and minimum values of the part, then find the maximum and minimum values of the right half, and then combine them to find the overall maximum and minimum values. This is a recursive process. For the left and right parts after division, this process is repeated until there is only one element or two elements left in the divided interval.
Given an array containing n For an integer array of elements, find its maximum value and second maximum value.
The idea is similar to the previous question. It also uses the divide and conquer method. No more details, just look at the code:
Given an array a of n integer elements, there is an element that appears more than n/2, find this element. It is said to be an interview question at Baidu.
Set a current value and a counter of the current value, initialize the current value to the first element of the array, the counter value is 1, and then traverse the entire array starting from the second element, for each traversed value a[ i].
If a[i]==currentValue, the counter value is increased by 1.
If a[i] != currentValue, the counter value is decremented by 1. If the counter value is less than 0, the current value is updated to a[i] and the counter value is reset to 1.
// Find the elements that appear more than half of the times in the array
int Find( int* a, int n)
{
int curValue = a[0] ;
int count = 1 ;
for (int i = 1; i
Another method is to sort the array first, and then take the middle element, because if the number of an element exceeds half, then the element must occupy the middle position of the array after the array is sorted.
Find the shortest distance between elements in the array
Given an integer array containing n elements, find the two elements x and y in the array that minimize the abs(x - y) value.
First sort the array, and then iterate through it once:
Copy the code The code is as follows:
int compare(const void* a, const void* b)
{
return *(int*)a - *(int*)b ;
}
void MinimumDistance( int* a, int n)
{
// Sort
qsort(a, n, sizeof(int), compare) ;
int i ; // Index of number 1
int j ; // Index of number 2
int minDistance = numeric_limits::max() ;
for (int k = 0; k < n - 1; ++k )
{
if (a[k + 1] - a[k] < minDistance)
{
minDistance = a[k + 1] - a[k] ;
i = a[k] ;
j = a[k + 1] ;
}
}
cout << "Minimum distance is: " << minDistance < < endl ;
cout << "i = " << i << " j = " << j << endl ;
}
Find the common elements of two ordered arrays
Given two ordered (non-descending) integer arrays a and b containing n elements, find their common elements, for example: a = 0, 1, 2, 3, 4 and b = 1, 3, 5, 7, 9, output 1, 3.
Make full use of the ordered nature of the array, use two pointers i and j to point to a and b respectively, compare a[i] and b[j], and move the pointer according to the comparison result, there are three situations as follows: :
a[i] < b[j], then i is increased by 1, and the comparison continues
a[i] == b[j], then both i and j are increased by 1, and the comparison continues
a[i]
Repeat the above process until i or j reaches the end of the array.
Copy code The code is as follows:
// Find the common elements of two arrays
void FindCommon (int* a, int* b, int n)
{
int i = 0;
int j = 0;
while (i < n && j < n)
{
if (a[i] < b[j])
++i ;
else if(a[i] == b[j])
{
cout << a[i] << endl ;
++i ;
++j ;
}
else// a[i] > b[j]
++j ;
}
}
There are other solutions to this problem, such as for any element in a, perform it in b Binary Search, because there are n elements in a, and doing Binary Search in b requires logn. So the time complexity of finding all the same elements is O(nlogn).
In addition, for the above method, as long as b is in order, it does not matter whether a is in order, because we are only doing Binary Search in b. If a is also ordered, then using the above method is a bit slow, because if the position of an element in a in b is k, then the position of the next element in a in b must be on the right side of k , so the search space this time can be narrowed based on the last search results, instead of still searching in the entire b. That is, if a and b are both ordered, the code can be modified as follows to record the position of the element in b during the last search as the starting point for the next search.
Find the common element of the three arrays
Given three integer arrays a, b and c containing n elements, find their smallest common element.
If the three arrays are all ordered, you can set three pointers to point to the heads of the three arrays, and then move the pointers based on the comparison of the values pointed by the three pointers until the common element is found.
Copy code The code is as follows:
// Common elements of three arrays - only find the smallest
void FindCommonElements(int a[], int b[], int c[], int x, int y, int z)
{
for(int i = 0, j = 0, k = 0; i < 🎜>else // a[i] >= b[j]
{
if(b[j] < c[k])
{
j++ ;
}
else // b[j] >= c[k]
{
if(c[k] < a[i])
{
k++ ;
}
else // c[k] >= a[i]
{
cout << c[k] << endl ;
return ;
}
}
}
}
cout << "Not found!" << endl ;
}
If three The arrays are all unordered. You can sort a and b first, and then perform a binary search in b and c for any element in c.
Copy code
The code is as follows:
// Find the unique common element in 3 arrays
// O(NlogN)
int UniqueCommonItem(int *a, int *b, int *c, int n)
{
// sort array a
qsort(a, n, sizeof(int), compare) ; // NlogN
// sort array b
qsort(b, n, sizeof( int), compare) ; // NlogN
// for each element in array c, do a binary search in a and b
// This is up to a complexity of N*2*logN
for (int i = 0; i < n; i++)
{
if(BinarySearch(a, n, c[i]) && BinarySearch(b, n, c[i]))
return c[i] ;
}
return - 1 ; // not found
}
You can also sort a, and then for b and Any element in c is binary searched in a.
Copy code The code is as follows:
// Find the unique common element in 3 arrays
// O(NlogN )
int UniqueCommonItem1(int *a, int *b, int *c, int n)
{
// sort array a
qsort(a, n, sizeof(int), compare) ; // NlogN
// Space for time
bool *bb = new bool[n] ;
memset(bb, 0, n) ;
bool *bc = new bool[n] ;
memset(bb, 0, n) ;
// for each element in b, do a BS in a and mark all the common element
for (int i = 0; i < n; i++) // NlogN
{
if(BinarySearch(a, n, b[i]))
bb[i] = true ;
}
// for each element in c, do a BS only if b[i] is true
for (int i = 0; i < n; i++) // NlogN
{
if(b[i] && BinarySearch(a, n, c[i]))
return c[i] ;
}
return - 1 ; // not found
}
The sorting and binary search code is as follows:
Copy the code The code is as follows:
// Determine whether a contains value k
bool BinarySearch(int *a, int n, int k)
{
int left = 0 ;
int right = n - 1 ;
while (left <= right)
{
int mid = (left + right) ;
if(a[mid] < k)
left = mid + 1 ;
if (a[mid] == k)
return true ;
else
right = mid - 1 ;
}
return false ;
}
// Compare function for qsort
int compare(const void* a, const void* b)
{
return *(int*)a - *(int*)b ;
}
To summarize, the problem of searching in an array can be handled in the following two situations:
If the given array is ordered, then Binary Search should be thought of first, so Requires O(logn).
If the given array is unordered, you should first think of sorting the array. Many sorting algorithms can sort the array in O(nlogn) time, and then use binary search. The total time complexity is still O(nlogn).
If you can do the above two points, most of the array search problems can be easily solved.
Find the only duplicate element in the array
Given an array containing 1001 elements, which stores integers between 1-1000, only one integer is duplicated, please find this number.
Find the sum of the entire array, and then subtract the sum of 1-1000. The code is omitted.
Find the element that appears an odd number of times
Given an integer array a containing n elements, in which only one element appears an odd number of times, find this element.
Because for any number k, there are k ^ k = 0, k ^ 0 = k, so if all the elements in a are XORed, then the XOR of the even number of elements becomes 0, leaving only the element with an odd number.
int FindElementWithOddCount(int *a, int n)
{
int r = a[0] ;
for (int i = 1; i
find array Pairs of numbers that satisfy the given sum in Element j in b satisfies i + j = d (d is known).
The two pointers i and j point to the beginning and end of the array respectively, and then traverse from both ends to the middle at the same time until the two pointers cross.
Copy code The code is as follows:
// Find the number pairs that satisfy the given sum
void FixedSum(int * a, int* b, int n, int d)
{
for (int i = 0, j = n - 1; i < n && j >= 0)
{
if (a[i] + b[j] < d)
++i ;
else if (a[i] + b[j] == d)
{
cout << a[i] << ", " << b[j] << endl ;
++i ;
--j ;
}
else // a[i] + b[j] > d
--j ;
}
}
Maximum subsegment sum
given an integer Type array a, find the maximum sum of consecutive sub-segments. If the sum is a negative number, it is calculated as 0, such as 1, 2, -5, 6, 8, then 6 + 8 = 14 is output.
Programming Zhuji. Not much to say about the classic questions on
Copy the code The code is as follows:
//Maximum sum of sub-arrays
int Sum(int* a, int n)
{
int curSum = 0;
int maxSum = 0;
for (int i = 0; i < n; i++)
{
if (curSum + a[i] < 0)
curSum = 0;
else
{
curSum += a[i] ;
maxSum = max(maxSum, curSum);
}
}
return maxSum;
}
Maximum subsegment Product
Given an integer number a, find the product of the largest continuous subsegment, such as 1, 2, -8, 12, 7, then the output is 12 * 7 = 84.
Similar to the maximum subsegment sum, pay attention to the case of negative numbers.
Copy code The code is as follows:
// Maximum product of sub-arrays
int MaxProduct(int *a, int n)
{
int maxProduct = 1; // max positive product at current position
int minProduct = 1; // min negative product at current position
int r = 1; // result, max multiplication totally
for (int i = 0; i < n; i++)
{
if (a[i] > 0)
{
maxProduct *= a[i];
minProduct = min(minProduct * a[i], 1);
}
else if (a[i] == 0)
{
maxProduct = 1 ;
minProduct = 1;
}
else // a[i] < 0
{
int temp = maxProduct;
maxProduct = max(minProduct * a[i] , 1);
minProduct = temp * a[i];
}
r = max(r, maxProduct);
}
return r;
}
Array circular shift
Circularly moving an array containing n elements to the right by k bits requires a time complexity of O(n), and only two additional Variables, this is a question I saw on Microsoft's The Beauty of Programming.
For example, if the array 1 2 3 4 is rotated right by 1 bit, it will become 4 1 2 3. It can be seen that the order of 1 2 3 has not changed before and after the shift, but has been exchanged with the position of 4, so it is equivalent First divide 1 2 3 4 into two parts 1 2 3 | 4, then reverse the order of 1 2 3, then reverse the order of 4 to get 3 2 1 4, and finally reverse the whole order to get 4 1 2 3.
Copy code The code is as follows:
// Reverse the elements between start and end in the buffer
void Reverse ( int buffer[], int start, int end )
{
while ( start < end )
{
int temp = buffer[ start ] ;
buffer[ start++ ] = buffer [ end ] ;
buffer[ end-- ] = temp ;
}
}
// Shift the array buffer containing n elements to the right by k bits
void Shift( int buffer[], int n, int k )
{
k %= n ;
Reverse( buffer, 0, n - k - 1) ;
Reverse( buffer, n - k, n - 1 ) ;
Reverse( buffer, 0, n - 1 ) ;
}
String reverse order
Given a character containing n elements Array a, reverse the order in place.
Maybe you think this is not about arrays, but about strings. Yes. But don’t forget that the question requires in-place reverse order, that is, no additional allocation of space is allowed, so the parameter must be in the form of a character array, because the string cannot be modified (here are only string constants in C/C++), so , it’s related to arrays, but it’s not an integer array, but a character array. Use two pointers to point to the first position of the character array, exchange their corresponding characters, and then move the two pointers toward the center of the array until they cross.
Copy code The code is as follows:
// String reverse order
void Reverse(char *a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
char temp = a[left];
a[left++] = a[right] ;
a[right--] = temp ;
}
}
Composition problem
Given a An integer array a containing n elements, randomly select m elements from it, and find all combinations. For example, the following example:
a = 1, 2, 3, 4, 5
m = 3
Output:
1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5
3 4 5
Typical permutation and combination problem, the backtracking method is preferred , in order to simplify the problem, we set the n element values in a to 1-n respectively.
Copy code The code is as follows:
// n select all combinations of m
int buffer[100];
void PrintArray(int *a, int n)
{
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
cout << endl ;
}
bool IsValid(int lastIndex, int value)
{
for (int i = 0; i < lastIndex; i++)
{
if (buffer[i] >= value)
return false;
}
return true;
}
void Select(int t, int n, int m)
{
if (t == m)
PrintArray(buffer, m);
else
{
for ( int i = 1; i <= n; i++)
{
buffer[t] = i;
if (IsValid(t, i))
Select(t + 1, n, m);
}
}
}
Merge two arrays
Given two ordered (non-descending) integer arrays a and b containing n elements. Merge the elements in the two arrays into the integer array c, removing duplicate elements and keeping c in order (not descending order). Examples are as follows:
a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8
Using the idea of merging sort, two pointers i, j and k point to arrays a and b respectively, and then compare the sizes of the elements corresponding to the two pointers. There are the following three situations:
a[i]
a[i] == b[j], then c[k] is equal to a[i] or b[j].
a[i] > b[j], then c[k] = b[j].
Repeat the above process until i or j reaches the end of the array, and then copy the remaining elements directly to the array c.
Copy code The code is as follows:
// Merge two ordered arrays
void Merge(int *a, int *b, int *c, int n)
{
int i = 0;
int j = 0;
int k = 0;
while (i < n && j < n)
{
if (a[i] < b[j])// If the element of a is small, insert the element in a into c
{
c [k++] = a[i] ;
++i ;
}
else if (a[i] == b[j])// If a and b elements are equal, insert both Either way, insert a
{
c[k++] = a[i] ;
++i ;
++j ;
}
else // a[i ] > b[j] // If the element in b is small, insert the element in b into c
{
c[k++] = b[j] ;
++j ;
}
}
if (i == n) // If a is traversed, process the remaining elements in b
{
for (int m = j; m < n; ++m)
c[k++] = b[m] ;
}
else//j == n, if b is traversed, process the remaining elements in a
{
for (int m = i; m < n; ++m)
c[k++] = a[m] ;
}
}
Rearrangement problem
Given an integer array a containing n elements, including 0 elements and non-0 elements, sort the array, requiring:
After sorting, all 0 elements are in front, and all non-zero elements are in after, and the relative position of non-zero elements remains unchanged before and after sorting.
Cannot use additional storage.
The example is as follows: input 0, 3, 0, 2, 1, 0, 0, output 0, 0, 0, 0, 3, 2, 1.
This sorting is not sorting in the traditional sense, because it requires that the relative position of non-zero elements before and after sorting remains unchanged. Perhaps it is more appropriately called sorting. We can traverse the entire array from back to front. When the element at a certain position i is a non-0 element, if a[k] is 0, then a[i] is assigned to a[k], and a[k] is assigned a value. is 0. In fact, i is the subscript of a non-zero element, and k is the subscript of a 0 element.
Copy code The code is as follows:
void Arrange(int* a, int n)
{
int k = n - 1 ;
for (int i = n - 1; i >= 0; --i)
{
if (a[i] != 0)
{
if (a[k] == 0)
{
a[k] = a[i] ;
a[i] = 0 ;
}
--k ;
}
}
}
http://www.bkjia.com/PHPjc/323992.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/323992.htmlTechArticleArray sum Given an integer array a containing n elements, find the sum of all elements in a. You may think it is very simple, yes, it is indeed simple, but why do you say it? There are two reasons...
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
