Make writing a habit together! This is the 11th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I plan to update the realization of all the code exercises of 23 Kingway data structure after class. Although the exam is generally written in pseudo-code, I still realized all of them because of obsessive-compulsive. The warehouse is here

  • The linear table

Then, 13

  • Find the smallest positive integer, so you don’t have to worry about negative numbers
  • So the idea is the same as the first solution on problem 12, which is sort of bucket sorting
  • Open a new array, subscript the value of the element, the value of the element is present
  • Time O(n), space O(n),It’s already an optimal solution, right?
int find_miss_min(SqList list) {
  // 1. Initialize an array of all zeros
  int tmp[list.length] = {0};

  // 2. The subscript corresponds to the element value, and the value corresponds to the element occurrence
  for (int i = 0; i < list.length; i++) {
    if (list.data[i] > 0 && list.data[i] <= list.length)
      tmp[list.data[i]]++;
  }

  // 3. Find the smallest positive integer
  int i;
  for (i = 1; i < list.length; i++) {
    if (tmp[i] == 0) 
      return i;
  }
  return i;
}
Copy the code

Then, 14

  • Violence, direct triple cycle!
  • One by one, find the smallest
  • Time complexity O(N3), time complexity O(1)
int find_min_distance(int A[], int B[], int C[], int n1, int n2, int n3) {
  int dmin = INT_MAX, d;
  for (int i = 0; i < n1; i++) {
    for (int j = 0; j < n2; j++) {
      for (int k = 0; k < n3; k++) {
        // Calculate the distance
        d = abs(A[i] - B[j]) + abs(B[j] - C[k]) + abs(C[k] - A[i]);
        // Update the minimum value
        if(d < dmin) dmin = d; }}}return dmin;
}
Copy the code

  • You know, absolute value is the distance along the number line

  • When a is equal to b is equal to c, the distance is minimal

  • When a<=b<=c, as shown in the figure

  • The thing that determines the size of D is the distance between C and A, so let’s fix c every time and find an A that minimizes the distance

  • Time complexity O(n), space complexity O(1)

// whether n1 is the smallest of the three numbers
bool find_min(int n1, int n2, int n3) {
  if (n1 <= n2 && n1 <= n3) return true;
  return false;
}

int find_min_distance2(int A[], int B[], int C[], int n1, int n2, int n3) {
  int dmin = INT_MAX, d, i = 0, j = 0, k = 0;
  while(i < n1 && j < n2 && k < n3) {
    // Calculate the distance
    d = abs(A[i] - B[j]) + abs(B[j] - C[k]) + abs(C[k] - A[i]);
    // Update the minimum value
    if (d < dmin) dmin = d;
		
    if (find_min(A[i], B[j], C[k])) i++;
    else if (find_min(B[j], C[k], A[i])) j++;
    else k++;
  }
  return dmin;
}
Copy the code
  • The sequence list has been completed, and the linked list will be updated tomorrow