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

  • Find duplicate elements that are more than half the number of elements in the array, so an array has at most one primary element
  • Violence is the trade of space for time, kind of like bucket sorting
  • Open a new array whose subscript corresponds to the value of the element, and the value corresponds to the number of elements.
  • Time complexity O(n), space complexity O(n)
int find_main(SqList list) {
  // 1. Initialize an array with all zeros by default
  int tmp[list.length] = {0};

  // 2.
  for (int i = 0; i < list.length; i++) {
    tmp[list.data[i]]++;
  }

  // 3. Iterate to find the main element
  for (int i = 0; i < list.length; i++) {
    if (tmp[i] > list.length / 2 ) 
      return i;
  }

  // 4. Return -1 if not found
  return - 1;
}
Copy the code
  • Second way: Let’s sort and then find the pivot elements
  • Count the number of occurrences of each element and determine if the current element is the main element if the following number is not a repeat element
  • Because of fast sorting, order nlogn time, order nlogn space.
  • This solution is worth up to 11 points out of 13, so don’t force the best solution
int find_main2(SqList list) {
  / / 1. Fast row
  sort(list.data, list.data+list.length);

  // 2. Count the number of occurrences of each element to find the main element
  int cnt = 1;
  for (int i = 0; i < list.length - 1; i++) {
    if (list.data[i+1] == list.data[i]) {
      cnt++;
    } else {
      if (cnt > list.length / 2)
        return list.data[i];
      cnt = 1; }}return - 1;
}
Copy the code
  • On the exam of this question (Ought probably probablyYou can omit the implementation of sorting that is irrelevant to the topic
  • Because the space required by each iteration of fast sorting is fixed, the number of recursive layers is the space complexity, so the average space complexity of fast sorting is O(logn).
  • The implementation of fast sorting is as follows:
void quick_sort(int l, int r) {
  if (l == r) return; 
  
  int x = a[(l+r)/2];     // 1. Pivot elements
	
  // 2. Divide into two pieces
  int i = l- 1, j= r+1;
  while (i < j) {
    while (a[++i] < x);		// Find the element greater than x on the left
    while (a[--j] > x);		// Find the element on the right-hand side less than x
    if (i < j) swap(a[i], a[j]); 	/ / swap
  }
	
  / / 3. Recursion
  quick_sort(l, j);
  quick_sort(j+1, r);
}
Copy the code
  • Optimal solution, pair to pair
  • Since the number of primary elements is more than half of the array, it cancels out all other elements and has a surplus
  • Time complexity O(n), space complexity O(1)
int find_main3(SqList list) {
  int c, cnt = 1;
  c = list.data[0];

  // 1. Select the candidate primary element
  for (int i = 1; i < list.length; i++) {
    if (list.data[i] == c) cnt++;
    else {
      if (cnt > 0) {
        cnt--;
      } else {
        c = list.data[i];
        cnt = 1; }}}// 2. Count the actual quantity
  if (cnt > 0) {
    cnt = 0;
    for (int i = 0; i < list.length; i++)
      if (list.data[i] == c) 
        cnt++;
  }
  
  // 3. Validate the main element
  if (cnt > list.length / 2) return c;
  return - 1;
}
Copy the code