Make writing a habit together! This is the 8th 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, the euro

  • Violent method, open an array, and then loop!
  • Not once, twice!
  • The parameters m and n are the lengths of two linear tables
  • Time O(m+n), space O(m+n)
void change(SqList &list, int m, int n) {
  [m, m+n-1] [m, m+n-1]
  SqList copied = list;
  int k = - 1;
  for (int i = m; i < m+n; i++) {
    copied.data[++k] = list.data[i];
  }
  for (int i = 0; i < m; i++) {
    copied.data[++k] = list.data[i];
  }
  list = copied;
}
Copy the code
  • Of course, there is another way to reverse the entire array, and then reverse the two linear tables
  • For example, [1, 2, 3, 4] is inverted into [4, 3, 2, 1], then one of the linear tables [4, 3] is inverted into [3, 4], and the other [2, 1] is inverted into [1, 2], resulting in [3, 4, 1, 2].
  • Time complexity O(m+n), space complexity O(1)
L =left, r=right
void reverse(SqList &list, int l, int r) {
  if (l > r || r > list.length) return;

  int mid = (l + r) / 2;
  // Pay attention to boundaries
  for (int i = 0; i <= mid - l; i++) {
    swap(list.data[l+i], list.data[r-i]); }}void change2(SqList &list, int m, int n) {
  // Pay attention to parameters
  reverse(list, 0, m+n- 1);
  reverse(list, 0, n- 1);
  reverse(list, n, m+n- 1);
}
Copy the code

2.2.3, 09

  • It’s an orderly, violent cycle
  • There are a lot of boundary conditions to consider, so it’s easy to make mistakes
  • Time complexity O(n), space complexity O(1)
void find_x2(SqList &list, int x) {
  // 1. Binary search for x
  int low = 0, high = list.length - 1, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    if (list.data[mid] == x) break;
    else if (list.data[mid] < x) low = mid + 1;
    else high = mid - 1;
  }

  // 2
  if(list.data[mid] == x && mid ! = list.length -1) {
    swap(list.data[mid], list.data[mid + 1]);
    return;
  }
  
  // select * from high where low>high
  list.length++;
  int i = list.length - 2;
  while (i > high) {
    list.data[i + 1] = list.data[i]; 
    i--;
  }
  list.data[i + 1] = x;
}
Copy the code
  • Optimization, using binary lookup, without the need to specifically record the value of I
  • When the lookup fails, High records to the last element less than x
  • Time complexity O(logn), space complexity O(1)
void find_x2(SqList &list, int x) {
  int low = 0, high = list.length - 1, mid;
  while (low <= high) {
    mid = (low + high) / 2;
    if (list.data[mid] == x) break;
    else if (list.data[mid] < x) low = mid + 1;
    else high = mid - 1;
  }

  // Found and not the last element
  if(list.data[mid] == x && mid ! = list.length -1) {
    swap(list.data[mid], list.data[mid + 1]);
    return;
  }

  / / not found
  list.length++;
  int i = list.length - 2;
  while (i > high) {
    list.data[i + 1] = list.data[i]; 
    i--;
  }
  list.data[i + 1] = x;
}
Copy the code