recursive

Example derivation

• Find the maximum value in the array recursively (using a stack)

• The method of finding midpoint is improved

  Mid = (left + right) / 2 //(left + right) / 2 //(right + left) // Mid = left + (right-left) >> 1 // Use bit operation to speed up the calculation

code

package com.example.demo.class01; Public class Code08_GetMax {public static void main(String[] args) {int arr[] = {1,2,4,3,2,8,6}; int c = 0; c = getMax(arr); System.out.println(c); } public static int getMax (int [] arr) {if (arr = = null | | arr. Length = = 0) {System. Out. Println (" input array unreasonable "); } return process(arr,0,arr.length - 1); } public static int process(int[] arr,int L,int R){ if(L == R){ return arr[L]; } //arr[L..R] base case int mid = L + ((r-l)>>1); int leftMax = process(arr,L,mid); int rightMax = process(arr,mid+1,R); return Math.max(leftMax,rightMax); }} / / 8Copy the code

Use of master publicity

• Used to analyze recursion, used to solve problems where subproblems are of uniform size

  T(N) = a*T(N/b) + O(N^d)

  1, log (b, a) > d – > complexity to O (N ^ log (b, a)) 2, the log (b, a) = d – > complexity is O (N ^ d * logN) 3, the log (b, a) < – > d complexity is O (N ^ d)

Merge sort

• The whole thing is just a simple sort, you order it on the left, you order it on the right, you order the whole thing

• The time is order N logN.

• The extra complexity is order N.

• code

  package com.example.demo.class01;

  import java.util.Arrays;

  public class MergeSort {

  public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } process(arr, 0, arr.length - 1); } public static void process(int[] arr, int L, int R) { if (L == R) { return; } int mid = L + ((R - L) >> 1); process(arr, L, mid); process(arr, mid + 1, R); merge(arr, L, mid, R); } public static void merge(int[] arr, int L, int M, int R) { int[] help = new int[R - L + 1]; int i = 0; int p1 = L; int p2 = M + 1; while (p1 <= M && p2 <= R) { help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= M) { help[i++] = arr[p1++]; } while (p2 <= R) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[L + i] = help[i]; } } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 ! = null) || (arr1 ! = null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length ! = arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] ! = arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); mergeSort(arr1); comparator(arr2); if (! isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!" ); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); mergeSort(arr); printArray(arr); }Copy the code

  }

Small and problem

• Definition: In an array, the sum of each number less than the preceding number is called the small sum of this number.

• This is the sum of (the number greater than me on the right * my own size), which is the same as the number given by the small sum

• res += arr[p1] < arr[p2] ? (r – p2 + 1) * arr[p1] : 0; P1 points to the number on the left, P2 points to the number on the right, and R is the rightmost boundary of the right part. R -p2 +1 is the number greater than the current left element, times the current element itself; Follow all the elements as described above and you end up with a small sum

• Example: [1, 3, 4, 2, 5], the number to the left of 1 is less than 1: none; The number to the left of 3 less than 3:1; The number to the left of 4 less than 4:1,3; The number to the left of 2 less than 2:1; Numbers less than 5 to the left of 5:1,3,4,2; Sum: 16

Use merge sort to solve small sum problems

• Merge sort, encounter the same element, first move left, is to ensure the stability of the program; In this case, the right element is moved first to determine the number of elements in the right block that are larger than the element pointed to by the left pointer
• The small sum is problematic in three places: sorting within the left block; Sort in the right block; Left and right blocks merge

code

package class02; public class Code02_SmallSum { public static int smallSum(int[] arr) { if (arr == null || arr.length < 2) { return 0; } return process(arr, 0, arr.length - 1); Public static int process(int[] arr, int L, int R) {if (L == R) {return 0;} public static int process(int[] arr, int L, int R) {return 0; } int mid = l + ((r - l) >> 1); return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r); } public static int merge(int[] arr, int L, int m, int r) { int[] help = new int[r - L + 1]; int i = 0; int p1 = L; int p2 = m + 1; int res = 0; while (p1 <= m && p2 <= r) { res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0; help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= m) { help[i++] = arr[p1++]; } while (p2 <= r) { help[i++] = arr[p2++]; } for (i = 0; i < help.length; i++) { arr[L + i] = help[i]; } return res; } // for test public static int comparator(int[] arr) { if (arr == null || arr.length < 2) { return 0; } int res = 0; for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { res += arr[j] < arr[i] ? arr[j] : 0; } } return res; } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 ! = null) || (arr1 ! = null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length ! = arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] ! = arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); if (smallSum(arr1) ! = comparator(arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!" ); }}Copy the code

• Similar to the reverse pair problem: if the number on the left is larger than the number on the right, they form an inverse pair, similar in principle

•   res += arr[p1] > arr[p2] ? (m - p1 +1) : 0;
    
  Copy the code

The Dutch flag

• Quick sort
• Given arr and num, place the number less than or equal to num on the left side of the array, and place the number greater than num on the right side of the array. The time complexity is O(N) and space complexity is O(1). Internal order is not required

​

• The array is divided into three parts, with num as the boundary, divided into less than or equal region, greater than region and undetermined region. The pointer points to the first element of the array and determines whether the element to which the pointer points is less than or equal to num. If the current number is swapped with the next number in the less than or equal area, then the less than or equal area moves to the right and the pointer moves to the right

• If the pointer points to an element greater than num, the pointer skips that element and moves to the right.

  package class02;

  public class Code05_NetherlandsFlag {

  public static int[] partition(int[] arr, int l, int r, int p) {
  	int less = l - 1;
  	int more = r + 1;
  	while (l < more) {
  		if (arr[l] < p) {
  			swap(arr, ++less, l++);
  		} else if (arr[l] > p) {
  			swap(arr, --more, l);
  		} else {
  			l++;
  		}
  	}
  	return new int[] { less + 1, more - 1 };
  }
  
  // for test
  public static void swap(int[] arr, int i, int j) {
  	int tmp = arr[i];
  	arr[i] = arr[j];
  	arr[j] = tmp;
  }
  
  // for test
  public static int[] generateArray() {
  	int[] arr = new int[10];
  	for (int i = 0; i < arr.length; i++) {
  		arr[i] = (int) (Math.random() * 3);
  	}
  	return arr;
  }
  
  // for test
  public static void printArray(int[] arr) {
  	if (arr == null) {
  		return;
  	}
  	for (int i = 0; i < arr.length; i++) {
  		System.out.print(arr[i] + " ");
  	}
  	System.out.println();
  }
  
  public static void main(String[] args) {
  	int[] test = generateArray();
  
  	printArray(test);
  	int[] res = partition(test, 0, test.length - 1, 1);
  	printArray(test);
  	System.out.println(res[0]);
  	System.out.println(res[1]);
  
  }
  Copy the code

  }

Second question

• If num is less than or equal to num, place it in the left side of the array. If num is equal to num, place it in the middle of the array. If num is greater than or equal to num, place it in the right side of the array.

​

• Divide the array into three parts, less-than, middle, and greater-than.

• The pointer is used to point to the first element of the array. If the number currently pointing to is less than num, the next element in the less than range is swapped sideways with the current value

• If the current pointer points to an element equal to num, the pointer skips and moves to the next location

• If the current pointer points to an element larger than num, then the previous element larger than the range is swapped with the element that the current pointer points to. The greater than range expands to the left, but the current pointer cannot be moved because the swapped elements and num are not known

  package class02;

  import java.util.Arrays;

  public class Code06_QuickSort {

  public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l < r) { swap(arr, l + (int) (Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); } } public static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; while (l < more) { if (arr[l] < arr[r]) { swap(arr, ++less, l++); } else if (arr[l] > arr[r]) { swap(arr, --more, l); } else { l++; } } swap(arr, more, r); return new int[] { less + 1, more }; } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { Int [] arr = new int[(int) ((maxSize + 1) * math.random ())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 ! = null) || (arr1 ! = null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length ! = arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] ! = arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); quickSort(arr1); comparator(arr2); if (! isEqual(arr1, arr2)) { succeed = false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!" ); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); quickSort(arr); printArray(arr); }Copy the code

  }

• The time complexity of fast sorting is order N logN.

​