Sequence table partial pseudo code
2. Delete the element with the minimum value from the sequence table (assuming unique) and return the deleted element by the function. The empty position is filled by the last element. If the sequence table is empty, an error message will be displayed and the operation will exit.
Writing thought:
typedef struct {
ElemType data;
int length; // Represents the length of the sequence table
}SqList;
1)Judge whether the sequence table length is 0. If yes, it means that the sequence table is empty, an error message is displayed, and exit
2)use e Receive the element to be deleted with L.data[L.length - 1]Replace element in original position,L.length Minus 1
// Pseudo code
void delMin(SqList &L,int pos,ElemType &value) {
// 1) Judge whether the sequence table is empty
if (L.length == 0) {
return false;
}
// Call the minimum function to obtain the minimum value and its corresponding subscript
findMin(L,pos,value);
L.data[pos] = L.data[L.length--];
return true;
}
3. Exchange a and b element values
Written thought: 1)Create an intermediate variable temp 2)temp = a;a = b;b = temp;
// Pseudo code
void swap(ElemType &a,ElemType &b) {
ElemType temp = a;
a = b;
b = a;
}
4. An efficient algorithm is designed to invert all the elements of the sequential Table L, and the spatial complexity of the algorithm is O(1)
Written thought: 1) Judgment sequence table L.length If it is an odd number or an even number, the odd number keeps the middle elements unchanged, and the other elements are exchanged from beginning to end; Even numbers are the exchange of the first and last elements 2) For exchange swap Intermediate variables of functions can be reused Then the complexity is: 1)Time complexity: O(n) 2)Space complexity: O(1)
// Pseudo code
void reverse(SqList &L){
if (L.length == 0){
return false; // Failed to return empty table directly
} else {
int i;
for (i = 0;i < L.length/2;i++){
swap(L.data[i],L.data[L.length - 1 - i]);
}
}
}
5. Using the sequence table to realize simple selection and sorting
Written thought:
1)from L.length Select the element with the smallest value among the elements and put it in the first position of the linear table. The next cycle starts from the rest L.length - 1 Find the element with the lowest value among the elements, and so on until the end of the loop.
2)After finding the minimum value and subscript in each round i Element exchange position at position
// Pseudo code
void choice_sort(SqList &L) {
int i,pos = 0,value = 0;
for (i = 0;i < L.length;i++) {
findMin(L,pos,value); // Get the minimum element subscript and element value from the unordered order table
swap(L.data[pos],L.data[i]);
}
}
6. For the sequential Table L with length N, write an algorithm with time complexity O(n) and space complexity O(1). The algorithm deletes all data elements with value x in the linear table
Written thought: 1)Traversal in reverse order, if L.data[L.length-1]by x Delete directly and L.length -= 1 2)If you traverse from back to front to a part in the middle x，Then call swap(L.data[i],L.data[L.length-1]),delete L.data[L.length-1]，And order L.length -= 1 3)Until the conditions are not met, exit the cycle, then L.length Representative non x Number of elements
// Pseudo code
void delx(SqList &L,int x) {
int i;
for (i = L.length - 1;i >= 0;i--) {
// The last element is exactly x, and the direct pointer moves forward 1 cell
if (L.data[L.length - 1] == x) {
L.length -= 1;
} else {
// x appears in the middle of the sequence table, exchanges with the last element, and then moves the pointer forward
if (L.data[i] == x) {
swap(L.data[i],L.data[L.length - 1]);
L.length -= 1;
}
}
}
}
7. Delete all elements whose bit order is between i and j from the sequence table
Written thought: 1)take j = max(i,j),i = min(i,j)；judge j - i Size, if j - i <= n - j，Then from i reach j Start traversal, using swap(L.data[k],L.data[n-k+i-1])；last L.length -= (j - i + 1); 2)if j - i > n - j，Then from j Traverse to n，conduct swap(L.data[k+1],L.data[k-j+i])，last L.length -= (j - i +1)
void deli_to_j(SqList &L,int i,int j) {
j = max(i,j);
i = min(i,j);
int k,n = L.length;
if (j - i <= n - j) {
for (k = i;k <= j;k++) {
swap(L.data[k],L.data[n-k+i-1]);
}
} else {
for (k = j;k <= n;k++) {
swap(L.data[k+1],L.data[k-j+i]);
}
}
L.length -= (j - i + 1);
}
8. Find out all elements with values between the given values s and t (s < T is required) in the ordered order table, and return the subscript range
Written thought: 1)The conventional idea is to traverse the sequence table in order to find the first greater than s Element subscript and first greater than t The range has been determined, but in this case, the time complexity is O(n)，Wasted ordered properties 2)If it can be determined by half search, the time complexity is O(logn),But the title says it's a sequence table...
int range_tag(SqList L,ElemType s,ElemType t,int &start,int &end) {
if (s >= t || L.length == 0) {
return false;
}
// Find the subscript of the first element greater than s
int pos = -1,i,next = -1;
for (i = 0;i < L.length;i++) {
if (L.data[i] >= s) {
pos = i;
}
}
// The whole table is smaller than s
if (pos == -1) {
return false;
}
// Find the last element smaller than t
pos = max(pos,0);
for (i = pos;i < L.length - 1;i++) {
if (L.data[i] <= t) {
next = i;
}
}
start = pos;
end = next;
return true;
}
9. Delete all elements whose values are between the given values s and t (s < T is required) from the ordered sequence table. If s or T is unreasonable or the sequence table is empty, an error message will be displayed and the operation will be exited.
Written thought: 1)judge L.length If it is 0, yes indicates that the sequence table is empty and returns false，Simultaneous judgment s>=t，Yes, return false 2)set up i 0, traverse the sequence table in turn, and compare the values of each element in turn. If L.data[i]stay s and t Between, assign to L.data[k],k Initial 0,be k+=1，Until the last element is traversed, L.length = k，delete k Element after
// Pseudo code
bool dels2t(SqList &L,int t,int s) {
if (L.length == 0 || s >= t) {
return false;
} else {
int k = 0,i;
for (i = 0;i < L.length;i++) {
if (L.data[i] < t && L.data[i] > s) {
L.data[k] = L.data[i];
k += 1;
}
}
L.length = k;
return true;
}
}
10. Delete all elements with duplicate values from the ordered order table, so that the values of all elements in the table are different.
Written thought: Example: 1, 2, 2, 2, 3, 3, 4 -- "1, 2, 3, 4" 1)Because the sequence table is ordered, elements with the same value must appear continuously 2)set up i Traverse from 1 to L.length-1，k Initially 1, if L.data[i] != L.data[i-1],L.data[k] = L.data[i];k += 1; 3)Traverse to the end k The indicated element is followed by a repeating element,L.length = k
bool delSameValue(SqList &L) {
if (L.length <= 1) {
return false;
} else {
int k = 1,i;
for (i = 1;i < L.length;i++) {
if (L.data[i] != L.data[i-1]) {
L.data[k] = L.data[i];
k += 1;
}
}
L.length = k;
return true;
}
}
Or idea 2:
Written thought: 1)Divide the table into A Table B Table; A The table is the first half of the ordered order table, B Table is the second half of the table 2)Initially, the table A There is only one element in the table, that is, the first element of the ordered order table B Have the rest n-1 Elements; 3)Use a watch A The last element of is associated with the table B Compare from the beginning. When there is inequality, append it to the table A On the tail 4)Repeat 3)Until the table B If it is blank, modify the length of the new table A Length of(Repetition time table B Then continue the position of the last comparison)
bool delSame(SqList &L) {
// Table empty, does not exist, delete
if (L.length == 0) {
return false;
}
// Pointers indexed in tables A, B
int indexA,indexB;
for (indexA = 0,indexB = 1;indexB < L.length;indexB++) {
if (L.data[indexA] != L.data[indexB]) {
L.data[++indexA] = L.data[indexB];
}
}
// The final table length is the length of table A
L.length = indexA + 1;
return true;
}
11. Merge the two ordered order tables into a new ordered order table, and the function returns the result order table.
Writing thought: In merge sort, we know that the best situation is that the last element of the previous ordered table is smaller than the first element of the next ordered table, so the comparison times are n，Splice the second table directly to the end of the first table. The worst case is crossover. For example, 1, 3, 5, 7 and 2, 4, 6, 8 compare 2 at this time n-1 second 1)The tail elements of two tables are aligned, and the elements with larger output values are compared to the new table. After outputting the elements, the tail elements are still aligned until one table is empty 2)Take out the elements in the remaining table and put them at the end of the new table, and the new table is called descending arrangement table
void addAB2C(SqList L1,SqList L2,SqList &L) {
// Create two pointers I and j to the footer of the two tables respectively
int i,j,k = 0;
// As long as one of the two tables is empty, exit the loop directly
for (i = L1.length - 1,j = L2.length - 1;i >= 0 && j >= 0;) {
if (L1.data[i] >= L2.data[j]) {
L.data[k++] = L1.data[i--];
} else {
L.data[k++] = L2.data[j--];
}
}
// Add the remaining table elements to L
if (i < 0) {
for (i = j;i >= 0;i--) {
L.data[k++] = L2.data[i];
}
} else {
for (j = i;j >= 0;j--) {
L.data[k++] = L1.data[j];
}
}
L.length = k;
}
Reference answer: compare from scratch
bool merge(SqList A,SqList B,SqList &C) {
if (A.length + B.length < MaxSize) {
return false;
}
// Index tables a, B and C respectively
int indexA = 0,indexB = 0,indexC = 0;
// When a table is processed, exit the loop
while (indexA < A.length && indexB < B.length) {
// Leftmost end of table A
if (A.data[indexA] <= B.data[indexB]) {
C.data[indexC++] = A.data[indexA++];
} else {
C.data[indexC++] = B.data[indexB++];
}
}
// A table has remaining contents, which are directly appended to the tail of table C
while (indexA < A.length) {
C.data[indexC++] = A.data[indexA++];
}
while (indexB < B.length) {
C.data[indexC++] = B.data[indexB++];
}
// Set the length of table C
C.length = indexC;
return true;
}
12. It is known that two linear tables (a1,a2,a3,..., am) and (b1,b2,b3,..., bn) are stored in one-dimensional array A[m+n]. Try to write a function to exchange the positions of two sequential tables in the array, that is, put (b1,b2,b3,..., bn) in front of (a1,a2,a3,..., am).
Written thought: The difficulty of this question is m and n Unknown size 1)m than n When large, for example:(1,2,3,4,5)(6,7,8)->(6,7,8)(1,2,3,4,5)； The violence method is relatively simple. You can create a new table for storage, and the space complexity is O(n)，Or move the table back n Bit, and then(b1,b2......,bn)Change to the empty place of the content bit in the previous table
void swap(int &a,int b) {
int c = a;
a = b;
b = c;
}
void exchange(SqList &L,int m,int n) {
int x = L.length,i;
// Linear table spaces have been applied for and cannot be added directly
SqList T;
T.length = 0;
for (i = 0;i < x;i++) {
T.data[i] = L.data[i];
T.length += 1;
}
for (i = x;i < x + n;i++) {
T.data[i] = 0;
T.length += 1;
}
for (i = L.length - 1;i >= 0;i--) {
// Move back n bits
T.data[i + n] = L.data[i];
}
// Start changing elements from L.length to L.length+n-1 to positions 0 to n-1
for (i = L.length;i <= L.length + n - 1;i++) {
swap(T.data[i-L.length],T.data[i]);
}
// Delete subsequent elements
T.length = x;
L = T;
}
Reference answer ideas:
Written thought: The original table is:(a1,a2,a3,...,am,b1,b2,b3...,bn) 1)Reverse the entire table:(bn,...b3,b2,b1,am,...,a3,a2,a1) 2)Before reversal n Elements:(b1,b2,b3,...,bn,...) 3)After reversal m Elements:(b1,b2,b3,...,bn,a1,a2,a3,...,am)
void reverse(SqList &L,int start,int end) {
if (start >= end || end >= L.length) {
return ;
}
// Perform inversion
for (int i = start;i <= (start + end)/2;++i) {
// exchange
swap(L.data[i],L.data[end - (i - start)]);
}
}
bool exchange(SqList &L,int m,int n) {
// illegal parameter
if (L.length != m + n) {
return false;
}
// Reverse the entire table
reverse(L,0,m+n-1);
reverse(L,0,n-1);
reverse(L,n,m+n-1);
return true;
}
13. The elements in the linear table (a1,a2,a3,..., an) are incremented in order and stored in the computer in order. It is required to design an algorithm to find the element with the value of x in the table in the least time. If it is found, it will be exchanged with the position of subsequent elements. If it is not found, it will be inserted into the table and the elements in the table will still be incremented and orderly
Written thought: 1)The minimum time required to find the value in the table is x Elements, and orderly, use half search(Dichotomy)lookup 2)set up low Is 0,high by n-1,Each calculation mid = (high + low)/2，Round down and compare x and L.data[mid]Size of, if x Xiaoze high = mid - 1，mid = (high + low)/2 Keep comparing until you find x And exchange it with subsequent elements or finally low == high representative x If it is not in the table, a new table is created and the loop will x Insert into high+1 Location
void swap(ElemType &a,ElemType &b) {
ElemType c = a;
a = b;
b = c;
}
int halfSearch(SqList &L,ElemType x) {
int high = L.length - 1;
int low = 0,mid;
while (low <= high) {
mid = (high + low) / 2;
// Find the element x and return the subscript directly
if (L.data[mid] == x) {
return mid;
} else if (L.data[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
// If x is not found, return the last subscript high less than x
return high;
}
// Insert the element x in the table where the subscript is index
bool insertWithIndex(SqList &L,int index,ElemType x) {
// Illegal insertion position
if (index < 0 || index > L.length) {
return false;
}
int i;
for (i = L.length - 1;i >= index;i--) {
L.data[i+1] = L.data[i];
}
// When a linear table is created, the space is fixed. Why can it be added directly
L.data[i+1] = x;
L.length += 1;
return true;
}
// Swap or insert x
void changeOrInsert(SqList &L,ElemType x) {
int i,pos;
pos = halfSearch(L,x);
// If x is found, it is exchanged with the successor
if (L.data[pos] == x && pos != L.length - 1) {
swap(x,L.data[pos+1]);
} else {
insertWithIndex(L,pos+1,x);
}
}
14. Suppose n (n > 1) integers are stored in one-dimensional array R, and an algorithm as efficient as possible in time and space is designed. Move the sequence stored in R to the left by P (0 < p < n), that is, transform the data in R from (X0,X1..., Xn-1) to (Xp,Xp+1,..., Xn-1,X0,..., Xp-1). Requirements:
- The basic design idea of the algorithm is given
- According to the design idea, the algorithm is described in C or C + + or Java language, and the key points are annotated
- The time complexity and space complexity of the inverse design algorithm are explained
Basic design idea: 1)More applications for linear tables p Storage space 2)set variable i From 0 to p Cycle so that L.data[n+i] = L.data[i] 3)set variable j from p Traverse to n+p,Before each element is overwritten p Elements in multiple locations L.data[j-p] = L.data[j] 4)Order table length L.length = n
bool leftMove(SqList &L,ElemType p,int n) {
// Judgment of illegal situation
if (p <= 0 || p >= n) {
return false;
} else {
int i,j;
for (i = 0;i < p;i++) {
// 0 to p-1 bit elements are stored at the end of the original table
L.data[n+i] = L.data[i];
L.length += 1;
}
for (j = p;j < n + p;j++) {
// The elements in the range from p to n+p-1 move forward by p bits as a whole
L.data[j-p] = L.data[j];
}
L.length = n;
return true;
}
}
Time complexity: O(n) Space complexity: O(p)
Reference answer:
Written thought: 1)Before reversal p Elements 2)Reverse all elements in the subsequent part 3)Whole table reversal
void reverse(SqList &L,int start,int end) {
// Direct end
if (start >= end || end >= L.length) {
return ;
}
// Perform inversion
for (int i = start;i <= (start + end)/2;++i) {
swap(L.data[i],L.data[end - (i - start)]);
}
}
void converse(SqList &R,int p) {
reverse(R,0,p-1);
reverse(R,p,R.length-1);
reverse(R,0,R.length-1);
}
15. For an ascending sequence s with length L(L ≥ 1), the number at the ceil(L/2) position is called the median of S. For example, if sequence S1=(11,13,15,17,19), the median of S is 15, and the median of the two sequences is the median of the ascending sequence containing all their elements. For example, if S2=(2,4,6,8,10), the median of S1 and S2 is 11. Now there are two equal length ascending sequences A and B. try to design an algorithm as efficient as possible in A given time and space to find the median of two sequences A and B. requirement:
- The basic design idea of the algorithm is given
- According to the design idea, the algorithm is described in C or C + + or Java language, and the key points are annotated
- The time complexity and space complexity of the inverse design algorithm are explained
Written thought: 1)Because two sequences A,B Is equal in length, and the median of the whole of the two sequences is searched, and A,B Both are in ascending order, so we can consider merging the two sequences into an ascending sequence 2)And in the process of sorting(L+1)The first element to insert a new sequence is A,B Median of two sequences
int findMid(SqList A,SqList B) {
SqList *C = (SqList *)malloc(sizeof(int) * (A.length + B.length));
// Pointers to sequences A and B, respectively
int i,j,k = 0;
// As long as there is an expression to the table length, it will exit the loop. Just insert the remaining tables into the end of table C
for (i = 0,j = 0;i < A.length && j < B.length;) {
if (A.data[i] <= B.data[j]) {
C.data[k++] = A.data[i++];
} else {
C.data[k++] = B.data[j++];
}
}
// Insert elements from remaining tables
while (i < A.length) {
C.data[k++] = A.data[i++];
}
while (j < B.length) {
C.data[k++] = B.data[j++];
}
C.length = k;
return C.data[A.length];
}
Time complexity: O(n) Space complexity: O(n)
Reference answer:
Written thought: Merge two ordered tables. The middle element in the merging process is the median
bool getMedian(SqList A,SqList B,ElemType &x) {
// illegal parameter
if (A.length != B.length) {
return false;
}
// indexC is the median position
int indexA = 0,indexB = 0,indexC = (A.length + B.length)/2;
// Exit the loop when a table is processed
while (indexA < A.length && indexB < B.length) {
// A leftmost end
if (A.data[indexA] <= B.data[indexB]) {
// Find median
if (--indexC == 0) {
x = A.data[indexA];
return true;
}
indexA++;
// B leftmost end
} else {
if (--indexC == 0) {
x = B.data[indexB];
return true;
}
indexB++;
}
}
// There is still something left in a table
while (indexA < A.length) {
// Find median
if (--indexC == 0) {
x = A.data[indexA];
return true;
}
indexA++;
}
while (indexB < B.length) {
if (--indexC == 0) {
x = B.data[indexB];
return true;
}
indexB++;
}
// A. When the length of B is 0, it will be executed here
return false;
}
Merge the two-stage ordered tables with a time complexity of O(n)，So the total time complexity is O(n) No additional space is consumed, and the space complexity is O(1)
16. An integer sequence A=(a0,a1,... an-1) is known, where 0 ≤ AI < n (0 ≤ I < n). If there is ap1 = ap2 =... apm = x and M > n / 2 (0 ≤ PK < n, 1 < K ≤ m), X is called the main element of A. For example, A=(0,5,5,3,5,7,5,5), then 5 is the main element; If A=(0,5,5,3,5,1,5,7), there is no main element in a. Assuming that n elements in a are stored in a one-dimensional array, please design an algorithm as efficient as possible to find the main element of A. If there is a main element, the element is output; Otherwise output - 1. Requirements:
- The basic design idea of the algorithm is given
- According to the design idea, the algorithm is described in C or C + + or Java language, and the key points are annotated
- Explain the time complexity and space complexity of your algorithm
Written thought: 1)According to the title description, we can see the so-called"Main element"Appears in the array at least n/2+1 2)Directly count the number of each element in the array. If it fails to meet the requirements, output-1，Otherwise, the output is greater than n/2 The value of that element In fact, this topic is used Python The dictionary thief is comfortable
void getMainElem(SqList L,int n) {
int *temp = (int *)malloc(sizeof(int) * n);
int i;
for (i = 0;i < n;i++){
// The initial record is 0
temp[i] = 0;
}
for (i = 0;i < L.length;i++) {
// Take the value as the key. Finally, you can see who the main element is through the key
temp[A[i]] += 1;
}
int max = temp[0],pos;
for (i = 1;i < n;i++) {
if (max < temp[i]) {
max = temp[i];
pos = i;
}
}
// Judge whether the conditions are met
if (pos > n/2) {
cout << pos;
} else {
cout << -1;
}
}
Time complexity: O(n) Space complexity: O(n)
17. Given an array containing n(n ≥ 1) integers, please design an algorithm as efficient as possible in time to find the smallest positive integer that does not appear in the array. For example, the minimum positive integer that does not appear in the array {- 5,3,2,3} is 1; The minimum positive integer that does not appear in the array {1,2,3} is 4. It is required:
- The basic design idea of the algorithm is given
- According to the design idea, the algorithm is described in C or C + + language, and the key points are annotated
- Explain the time complexity and space complexity of your algorithm
Written thought: 1)The maximum number of positive integers in the array is n Set the loop from 1 to n+1，The positive integer not encountered in the middle is the smallest positive integer that does not appear
void findMinNum(SqList &L) {
int i,n = L.length,j;
// Traversal from 1 to n + 1
for (i = 1;i <= n + 1;i++) {
// Later, judge whether this positive integer appears according to the tag
int tag = false;
for (j = 0;j < n;j++) {
if (L.data[j] == i) {
tag = true;
break;
}
}
// It means that the number i is not traversed and output directly
if (!tag) {
cout << "The minimum positive integer that does not appear is:" << i << endl;
break;
}
}
}
Time complexity: O ( n 2 ) O(n^2) O(n2)
Space complexity: O ( 1 ) O(1) O(1)
Reference answer: note how the answer limits the existence of super large positive integers in the original array, resulting in failure to create an appropriate array
Written thought: Request an array temp,Size n，The initial value of all elements is 0 Traversal table A: 1)Current element x Value at 1 n:temp[x-1] = 1 2)otherwise:No operation final: 1)existence temp[i] == 0;The smallest positive integer that does not appear is the first 2)Otherwise, the smallest positive integer that does not appear is n+1
int getMinPositiveInteger(int A[],int n) {
// Construct auxiliary array
int *temp = (int *)malloc(sizeof(int) * n);
// Initialize to 0
memset(temp,0,sizeof(int) * n);
int i;
for (i = 0;i < n;i++) {
// Between 1... n, set the array temp
if (A[i] >= 1 && A[i] <= n) {
temp[A[i] - 1] += 1;
}
}
// Found the first temp[i] with a value of 0
for (i = 0;i < n;i++) {
// eureka
if (!temp[i]) {
break
}
}
// Find here. If all the temp arrays are not 0, the evaluated value is i+1
return i + 1;
}
Time complexity:
O
(
n
)
O(n)
O(n)
Space complexity:
O
(
n
)
O(n)
O(n)
18. Given an array of positive integers, calculate the maximum difference between two elements in the array. It is required that the difference can only be calculated by subtracting the front element from the rear element
Written thought: 1)The last element can be the same as the previous element n-1 Make a difference between elements, select the largest value and store it in the auxiliary array temp in 2)Cycle from back to front according to 1)Operation fill temp 3)ergodic temp，Find the maximum value, which represents the maximum difference between the two elements in the array
void calculate(SqList L) {
int n = L.length;
// Construct auxiliary array
int *temp = (int *)malloc(sizeof(int) * n);
// Array initialized to 0
memset(temp,0,sizeof(int)*n);
int i,j,max;
for (i = n - 1;i >= 0;i--) {
max = L.data[1] - L.data[0];
for (j = i - 1;j >= 0;j--) {
if (max < L.data[i] - L.data[j]) {
max = L.data[i] - L.data[j];
}
}
// Find one element in each round and store it in temp
temp[i] = max;
}
// Start traversing temp to find the element with the largest value
max = temp[0];
for (i = 0;i < n;i++) {
if (max < temp[i]) {
max = temp[i];
}
}
cout << "The maximum difference between two elements in the array is:" << max << endl;
}
Time complexity:
O
(
n
2
)
O(n^2)
O(n2)
Space complexity:
O
(
n
)
O(n)
O(n)
Reference answer:
Written thought: The maximum difference must be generated from the previous minimum value, so you can do this: Traverse the array, assuming that the current traversal position is i 1)Record history(0,...i-1)The minimum value is minValue，The maximum difference in recorded history is maxDifference 2)The current difference is:prices[i]-minValue，If this value is higher than maxDifference Big, then update maxDifference Is the value After traversal, maxDifference Is the maximum difference
// Calculate the maximum difference between the rear element and the front element
int getMaxDifference(int A[],int n) {
// When the array is empty
if (n <= 0) {
return 0;
}
// The first element of initialization is the minimum value, and the maximum gap in history is 0
int minValue = A[0];
int maxDifference = 0;
// Processing follow-up
for (int i = 1;i < n;i++) {
// Smaller values are generated and updated
// This value minus minValue must be negative, so you don't have to calculate the difference
if (A[i] < minValue) {
minValue = A[i];
} else {
maxDifference = A[i]-minValue > maxDifference?A[i]-minValue:maxDifference;
}
}
return maxDifference;
}
Time complexity:
O
(
n
)
O(n)
O(n)
Space complexity:
O
(
1
)
O(1)
O(1)
19. Define triples ( a , b , c ) (a,b,c) (a,b,c)( a , b , c a,b,c a. B, C are positive numbers) D = ∣ a − b ∣ + ∣ b − c ∣ + ∣ c − a ∣ D = \vert a - b\vert + \vert b - c\vert + \vert c - a\vert D = ∣ a − b ∣ + ∣ b − c ∣ + ∣ c − a ∣. Three non empty integer sets are given S 1 , S 2 , S 3 S1,S2,S3 S1, S2 and S3 are stored in three arrays in ascending order. Please design an algorithm as efficient as possible to calculate and output all possible triples ( a , b , c ) ( a ∈ S 1 , b ∈ S 2 , c ∈ S 3 ) (a,b,c)(a∈S1,b∈S2,c∈S3) (a,b,c)(a ∈ S1,b ∈ S2,c ∈ S3). for example S 1 = { − 1 , 0 , 9 } , S 2 = { − 25 , − 10 , 10 , 11 } , S 3 = { 2 , 9 , 17 , 30 , 41 } S1 = \{{-1,0,9\}},S2 = \{{-25,-10,10,11\}},S3 = \{{2,9,17,30,41\}} S1 = {− 1,0,9},S2 = {− 25, − 10,10,11},S3={2,9,17,30,41} then the minimum distance is 2 and the corresponding triplet is ( 9 , 10 , 9 ) (9,10,9) (9,10,9), requirements:
- The basic design idea of the algorithm is given
- According to the design idea, the algorithm is described in C or C + + language, and the key points are annotated
- Explain the time complexity and space complexity of your algorithm
Written thought: 1)To achieve the minimum distance, the observation shows that the difference between the three data needs to be as small as possible 2)Solve with violence method
// Find absolute value function
int frac(int a,int b) {
int c = a - b;
return (c >= 0 ? c : 0 - c);
}
void findMindistance(int A[],int B[],int C[],int a,int b,int c) {
int i,j,k,min = frac(A[0],B[0]) + frac(A[0],C[0]) + frac(B[0],C[0]);
int posa,posb,posc;
for (i = 0;i < a;i++) {
for (j = 0;j < b;j++) {
for (k = 0;k < c;k++) {
if (min < frac(A[i],B[j]) + frac(A[i],C[k]) + frac(B[j],C[k])) {
min = frac(A[i],B[j]) + frac(A[i],C[k]) + frac(B[j],C[k]);
posa = A[i];
posb = B[j];
posc = C[k];
}
}
}
}
cout << "The minimum distance is:" << min << endl;
cout << "The corresponding triples are:(" << posa << ", " << posb << ", " << posc << ")" << endl;
}
Time complexity:
O
(
n
3
)
O(n^3)
O(n3)
Space complexity:
O
(
1
)
O(1)
O(1)
Reference answer:
Written thought: 1)Calculates the initial value with the first element of three arrays D value 2)Update the smallest of the three arrays to the value of the next bit of the corresponding array, and then recalculate D value 3)Repeat 2)Until one of the arrays is processed, the smallest array is recorded in the process D value After D Value is what you want
typedef struct {
// Triplet
int a,b,c;
int value;
}TripleDistance;
// Calculate 2max(|a-b|,|a-c|,|b-C |)
int calc2Max(int a,int b,int c) {
int maxV = abs(a - b);
if (maxV < abs(b - c)) {
maxV = abs(b - c);
}
if (maxV < abs(a - c)) {
maxV = abs(a - c);
}
return 2 * maxV;
}
// Minimum element corresponding subscript + 1
void updateIndex(int a,int b,int c,int &index1,int &index2,int &index3) {
int minV = a;
if (minV > b) {
minV = b;
}
if (minV > c) {
minV = c;
}
if (minV == a) {
index1 += 1;
} else if (minV == b) {
index2 += 1;
} else {
index3 += 1;
}
}
// Solve minimum distance
TripleDistance minDistance(int S1[],int S2[],int S3[],int n1,int n2,int n3) {
TripleDistance minDT;
// Initialize the first element
int index1 = 0,index2 = 0,index3 = 0;
minDt.a = S1[index1];
minDT.b = S2[index2];
minDT.c = S3[index3];
minDT.value = calc2Max(S1[index],S2[index],S3[index]);
// Add 1 to the subscript of the array where the minimum value is located
updateIndex(S1[index1],S2[index2],S3[index3],index1,index2,index3);
// Processing subsequent elements
// An array ends when it is processed
while (index1 < n1 && index2 < n2 && index3 < n3) {
// Calculate new D value
int d = calc2Max(S1[index1],S2[index2],S3[index3]);
// Resulting in smaller
if (d < minDT.value) {
minDT.value = d;
minDT.a = S1[index1];
minDT.b = S2[index2];
minDT.c = S3[index3];
}
//Update the subscript according to the calculation results
updateIndex(S1[index1],S2[index2],S3[index3],index1,index2,index3);
}
// Return results
return minDT;
}
Time complexity: O ( n 1 + n 2 + n 3 ) O(n1 + n2 +n3) O(n1+n2+n3)
Space complexity: O ( 1 ) O(1) O(1)