Summary of some common operations on php arrays

Array 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 should you say it? There are two reasons. First, this question requires the use of recursion, using only one line of code. Second, this is the first interview question I encountered in my life, and it has a special meaning.

To put it simply, there are two situations:

If the number of array elements is 0, then the sum is 0.
If the number of elements in the array is n, then first find the sum of the first n - 1 elements, and then add a[n - 1].
Copy code The code is as follows:
//Array sum
int sum(int *a, int n)
{
return n == 0 ? 0 : sum(a, n - 1) + a[n - 1];
}

Find the maximum and minimum values ​​of the array
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 first find the maximum value of the left half. value and minimum value, then find the maximum value and minimum value of the right half, and then combine them to find the overall maximum value and minimum value. 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.
Copy code The code is as follows:
// Find the maximum and minimum values ​​of the array, the return value is maxValue and minValue
void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue)
{
if(l == r) // There is only one element between l and r
{
maxValue = a[l] ;
minValue = a[l] ;
return ;
}

if(l + 1 == r) // There are only two elements between l and r
{
if(a[l] >= a[r])
{
maxValue = a[l] ;
minValue = a[r] ;
}
else
{
maxValue = a[r] ;
minValue = a[l] ;
}
return ;
}

int m = (l + r) / 2 ; // Find the midpoint

int lmax ; // Left half Partial maximum value
int lmin; // Minimum value of the left half
MaxandMin(a, l, m, lmax, lmin); // Recursive calculation of the left half

int rmax; // Maximum value of the right half Value
int rmin; // The minimum value of the right half
MaxandMin(a, m + 1, r, rmax, rmin); // Recursively calculate the right half

maxValue = max(lmax, rmax); // The total maximum value
minValue = min(lmin, rmin); // The total minimum value
}


Find the maximum value and second maximum value of the array
Given an integer array containing n elements, find its maximum value and the second largest 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:

Copy the code The code is as follows:
// Find the maximum value and the second largest value of the array, and the return value is between max and second in
void MaxandMin(int *a, int left, int right, int &max, int &second)
{
if(left == right)
{
max = a[left] ;
second = a[left] ;
}
else if(left + 1 == right)
{
max = a[left] > a[right] ? a[left] : a[right] ;
second = a[left] < a[ right] ? a[left] : a[right] ;
}
else
{
int mid = left + (right - left) / 2 ;

int leftmax ;
int leftmin ;
MaxandMin(a, left, mid , leftmax, leftmin) ;

int rightmax ;
int rightmin ;
MaxandMin(a, mid + 1, right, rightmax, rightmin) ;

max = leftmax > rightmax ? leftmax : rightmax ;
second = leftmax < rightmax ? leftmax : rightmax ;
}
}


Find the elements in the array that appear more than half of the time
Given an array a of n integer elements, one element 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.
Copy the code The code is as follows:
//Find the elements that appear more than half the time 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 an array
Given an integer array containing n elements, find the two elements x and y in the array that minimize the value of abs(x - y).

First sort the array, and then traverse it once:

Copy 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 the common elements Elements, such as: 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 increases by 1, continue to compare
a[i] == b[j], then both i and j increase by 1, continue to compare
a[i]
Repeat the above process until i or j reaches the end of the array.

Copy the code The code is as follows:
//Find the common elements of the 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. For example, for any element in a, perform a Binary Search on it in b, because there are n elements in a, and performing a 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 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 < x && j < y && k < z;)
{
if(a[i] < b[j])
{
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 The three 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 the 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 any element in b and c is in a Perform a binary search.
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 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, for the problem of searching in an array, It can be handled in the following two situations:

If the given array is in order, then you should first think of Binary Search, which 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 repeated, 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 elements that appear 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, k ^ k = 0, k ^ 0 = k, so all the elements in a are XORed, then the even number of elements will become 0 after XOR, leaving only The element with an odd number is placed.

int FindElementWithOddCount(int *a, int n)
{
int r = a[0] ;

for (int i = 1; i
Find the number pair in the array that satisfies the given sum
Given two numbers with Ordinal integer arrays a and b each have n elements. Find the number pairs in the two arrays that satisfy the given sum, that is, for element i in a and element j in b, satisfy 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 until the two pointers cross.
Copy code The code is as follows:
// Find the number pair that satisfies 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 sum of sub-segments
Given an integer array a, find the sum of the largest continuous sub-segments. If the sum is a negative number, it is calculated as 0, such as 1, 2, -5, 6, 8, then output 6 + 8 = 14.

A classic question on programming, not much to say.
Copy code The code is as follows:
//The 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 subarrays
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 shifting an array containing n elements by k bits to the right, the required time complexity is O(n), and Only two additional variables can be used. This is a question seen on Microsoft's The Beauty of Programming.

For example, if the array 1 2 3 4 is circularly shifted 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. It is just exchanged with the position of 4, so it is equivalent to 1 2 3 First divide 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 overall order to get 4 1 2 3.
Copy the code The code is as follows:
//Reverse the order of 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 array a containing n elements, reverse it 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 ;
}
}

Combination problem
Given an integer array containing n elements a, take any 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

A 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 the 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 containing n elements and b. Merge the elements in the two arrays into the integer array c, removing duplicate elements and keeping c in order (not descending order). The example is as follows:

a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8

Using the idea of ​​merge sort, the two pointers i, j and k point to the arrays a and b respectively, and then compare the two The pointer corresponds to the size of the element. There are three situations:

a[i]
a[i] == b[j], then c[k] can be 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 elements of a are small, insert the elements in a into c
{
c[k++] = a[i] ;
++i ;
}
else if (a[i] == b[j])// If the a and b elements are equal, both can be inserted. Insert a here
{
c[k++] = a[i] ;
++i ;
++j ;
}
else // a[i] > b[j] // If the element in b is small, Then insert the elements in b into c
{
c[k++] = b[j] ;
++j ;
}
}

if (i == n) // If a is traversed, process the remaining items in b Elements of
{
for (int m = j; m < n; ++m)
c[k++] = b[m] ;
}
else//j == n, if b is traversed, process a The remaining elements in
{
for (int m = i; m < n; ++m)
c[k++] = a[m] ;
}
}

Rearrangement problem
Given n elements An integer array a of elements, including 0 elements and non-0 elements. To sort the array, the requirements are:

After sorting, all 0 elements come first, all non-zero elements come last, and the relative position of the non-zero elements remains unchanged before and after sorting. .
Cannot use additional storage space.
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 ;
}
}
}