Data algorithm and structure
Constant operation
Independent of the amount of data, fixed time operations are constant operations, called big O (letter O), which refers to the awareness of the upper limit, that is, the most time-consuming and worst case
Addition, subtraction, multiplication and division, bit operation and array addressing are constant operations. Finding the nth element in the linked list is not a constant operation
log: Base on 2
lg: base 10
ln: Base on e
Time complexity
In the constant expression (estimated according to the worst case), as long as the high-order term, do not use the low-order term, and ignore the expression of the coefficient of the high-order term
There are also two time complexity expressions: the average time complexity O, the middle horizontal line, the time complexity in the best case, and the symbol of ohm
For example, aN^2 + bN^2 + c time complexity bit O(N^2)
To evaluate the quality of an algorithm flow, first look at the time complexity index, and then analyze the actual running time under different data samples, that is, 'constant term time'
O(logN)=O(log2N). By default, 2 is the bottom and no writing is omitted. If other numbers, such as 3, are the bottom, O(log3N) cannot be omitted
Extra space complexity
There is O(1) to indicate that the space is a fixed size, independent of the data sample size, O(N)
Or operation
The same is 0, the difference is 1, and there is no carry addition
- Nature 1
- 0^N=N:0 or any number, get the number itself,
- N^N=0: any number or itself, get 0,
- Property 2
- Satisfy commutative law and associative law, (explained by non carry addition)
- a^b=b^a
- (a^b)^c=a^(b^c)
- Satisfy commutative law and associative law, (explained by non carry addition)
- Property 3
- Any number of figures can be obtained from the above two articles. Or, who comes first and who comes later, the result is the same
Title:
-
In an array, one number appears odd times and the other numbers appear even times. Find the number that appears odd times?
All the numbers are processed or eor is obtained
-
In an array, two numbers appear odd times, and other numbers appear even times. Find the numbers that appear odd times?
Let these two numbers be a, B, a= b. Use eor or all numbers to get eor=a^b because a= b. So eor= 0, so one bit of eor binary must be 1. Find the value of the last position of eor Extract the lowest 1 , if it is the 8th place, then the 8th places of a and b must be 1 and 0 respectively
Then eor1 is used to remove all the numbers, but only the number with the 8th bit of 0 (1 is also OK), in order to exclude a or B (the last binary bit of EOR is 1 to distinguish a and b). Of course, it doesn't matter to exclude other numbers, because the occurrence of other numbers even times doesn't affect the result, so eor1 is equal to a or B
Now there is eor=a^b, and eor1 is equal to one of them, then eor^eor1 is equal to another number
Then traverse the element E in the array. Use x=e^c=e^a^b to traverse the array e1 backward. If e1==x exists, then a=e, b=e1=x
// When using or exchanging array elements, do not exchange the same position, otherwise the value of the position will be set to 0
int[] arr = {50, 60};
int i = 0;
int j = 0;
arr[i] = arr [i] ^ arr[j];
arr[j] = arr [i] ^ arr[j];
arr[i] = arr [i] ^ arr[j];
//Two subscripts point to the same position of the array. After exchange, the value of this position becomes 0
System.out.println("Arrays.toString(arr) = " + Arrays.toString(arr));// [0, 60]
// If two numbers are used or exchanged, the two numbers must be two spaces, otherwise the result becomes 0
int a = 17;
int b = a; // The exchange can be completed. b is a newly opened space, not pointing to A. in java, the value stored in the basic type variable is always a value, not a reference pointer
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("a = " + a);
System.out.println("b = " + b);
class Num {
int n;
Num(int n) {
this.n = n;
}
int get() {return n;}
void set(int n) {this.n = n;}
}
// Error example of swapping 0 at the same location in a reference object
Num n1 = new Num(17);
Num n2 = new Num(17); // Num n2 = n1; If you point to the same area, the exchange cannot be completed, and no matter what the original value is, the value becomes 0
n1.set(n1.get() ^ n2.get());
n2.set(n1.get() ^ n2.get());
n1.set(n1.get() ^ n2.get());
System.out.println("n1.get() = " + n1.get());
System.out.println("n2.get() = " + n2.get());
binary digit
Take inverse plus 1 and add yourself (~ A + 1) & A
Select sort
(time complexity O(n^2))
Select a minimum number to put in position 0, then select the remaining number to put in position 1, and complete the sorting of 1 position at a time
Bubble sorting
(time complexity O(n^2))
Starting from position 0, compare with the next number every time. If the conditions are met, exchange. Determine the last number in each round, because this number is equivalent to comparing with all numbers.
Equivalent to queuing according to height.
Insert sort
(time complexity O(n^2))
The time required for insertion sorting depends on the initial order of input elements. The more ordered the array, the faster the insertion sorting.
When the number of inversions in the array (two elements in the array in reverse order) is small, the insertion sort may even be faster than all other sorting algorithms.
Time complexity in the best case (such as ordered array) O(n) worst case (such as inverted array) O(n^2) space complexity O(1)
The position of subscript 0 has been sorted. Starting from 1, select this number. If it is smaller than the number on the left, it will be exchanged. Otherwise, select the next number. The left side of the selected number is sorted every time
It is equivalent to grasping cards when playing cards. No matter what the first card is, it has been sorted. Grasp one card at a time and compare it from right to left until it is inserted into the appropriate position.
for(int i = 1; i < arr.length; i++) {
for(int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
arr[j] = arr[j] ^ arr[j - 1];
arr[j - 1] = arr[j] ^ arr[j - 1];
arr[j] = arr[j] ^ arr[j - 1];
}
}
Merge sort
Time complexity O(nlogn)
Space complexity O(n), i.e. additional space is required to store auxiliary arrays
Merge two ordered arrays into a larger ordered array.
It can merge from top to bottom and from bottom to top.
The process of merging two sorted arrays in place:
Purpose: merge the sorted arr [lo... Mid] and sorted arr [mid + 1... Hi]
Copy the original array arr [lo... Hi] into the auxiliary array aux [lo... Hi], and the two pointers go back from the position lo and mid+1 respectively. Compare the two values and put the smaller values into arr [] in turn
Time optimization:
- Using insert sort to process small-scale subarrays (for example, the length is less than 15) can shorten the running time, generally saving 10% ~ 15% of the time.
- Add a judgment condition. If arr [mid] < = arr [mid + 1], it means that the two arrays do not need to be merged, and the merge method can be skipped.
// master formula: a=2 (two sub calls), B = 2 (sub calls are two-thirds of N), d=1 (merge), T(N)=2T(N/2)+O(N);
// According to: log (B, a) = D - > O (n ^ D * log (n)), the time complexity: O(NlogN) [algorithm better than O(N^2)]
private static void mergeSort(int[] arr, int left, int right) {
// You can judge the length of the array. If it is small, you can use other O(N^2) sorting algorithms
if (left >= right) return; // Do not sort below 2 elements
int mid = left + ((right - left) >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
if(arr[mid] <= arr[mid + 1]) return; //Reduce unnecessary merge calls by judging the connection location
int[] merge = merge(arr, left, mid, right);
System.arraycopy(merge, 0, arr, left, merge.length);
}
private static int[] merge(int[] src, int left, int mid, int right) {
int[] desc = new int[right - left + 1];// The new space holds the two sub arrays that have been sorted
int p2 = mid + 1; // Left points to the left array and p2 points to the right array
for (int i = 0; i < desc.length; i++) { // Fill new array
if (left > mid) { // Each time you put in a number, it is impossible to cross the boundary at the same time. When one side crosses the boundary, the other side copies it directly
System.arraycopy(src, p2, desc, i, right - p2 + 1);
return desc;
}
if (p2 > right) {
System.arraycopy(src, left, desc, i, mid - left + 1);
return desc;
}
desc[i] = src[left] > src[p2] ? src[p2++] : src[left++];
}
return desc;
}
public static void main(String[] args) {
int testCount = 30000;
for (int i = 0; i < testCount; i++) {
int length = 1000;
int scale = 20;
test(length, scale);
}
}
public static void test(int length, int scale) {
int[] source = randomArr(length, scale);
System.out.println("Arrays.toString(source) = " + Arrays.toString(source));
int[] clone = source.clone();
Arrays.sort(source);
mergeSort(clone, 0, clone.length - 1);
try {
compare(source, clone);
} catch (Exception e) {
System.out.println("Arrays.toString(source) = " + Arrays.toString(source));
System.out.println("Arrays.toString(clone) = " + Arrays.toString(clone));
throw e;
}
}
public static void compare(int[] arr, int[] other) {
for (int i = Math.max(arr.length, other.length) - 1; i > -1; i--) {
if (arr[i] != other[i]) throw new RuntimeException("compare failed!");
}
}
public static int[] randomArr(int length, int scale) {
int[] arr = new int[length];
scale += 1;
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * scale) - (int) (Math.random() * scale);
}
return arr;
}
Seek small sum
In an array, the numbers on the left of each number that are smaller than the current number are accumulated, which is called the small sum of the array. Find the small sum of each array?
In an array, the sum of all smaller elements on the left of any element is the small sum of the element, and the sum of all elements is the small sum of the array
Conversely: how many numbers on the right of a number are larger than it, this number will produce how many small sums, so
Using the merge sorting method can easily find the small sum. In the process of merge, the two pointer positions of the two arrays are compared, because the two arrays are already in good order. If the elements on the left are small, the number of small sums produced by this element can be obtained by calculating the number of remaining elements on the right, which does not need to be compared with all elements on the right
// Own realization
public static void main(String[] args) {
System.out.println(smallSum(new int[]{7, 8, 9, 2, 5}));
}
public static int smallSum(int[] arr) {
//return merge(arr.clone(), 0, arr.length - 1);
int[] clone = arr.clone();
try {
return merge(clone, 0, arr.length - 1);
} finally {
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(clone));
}
}
// arr not only needs to be well ordered, but also requires small sum
private static int merge(int[] arr, int left, int right) {
if (left >= right) return 0;
int mid = ((right - left) >> 1) + left;
return merge(arr, left, mid) + merge(arr, mid + 1, right) + merge(arr, left, mid, right);
}
private static int merge(int[] arr, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int left0 = left;
int p2 = mid + 1;
int smallSum = 0;
for (int i = 0; i < tmp.length; i++) {
if (left > mid) { // When there are no elements on the left, there will be no small sum, and the remaining elements on the right are ordered and larger than those in tmp
System.arraycopy(tmp, 0, arr, left0, i);// left0 can also be obtained through i and mid
return smallSum;
}
if (p2 > right) { // The remaining number is the largest. The remaining elements of the left array are copied to the rightmost of the right array
int leftRemain = mid - left + 1;
/**
* Worry about data loss due to range intersection during copying
* TODO idea Alarm "Copying to the same array with intersecting ranges"
* Inspection info: Reports suspicious calls to System.arraycopy(). Warnings reported by this inspection are:
* - source or destination which are not of an array type.
* - source and destination have a different type.
* - copied chunk length is always bigger than src.length - srcPos.
* - copied chunk length is always bigger than dest.length - destPos.
* - ranges always intersect in case, when source and destination is the same array.
*
* After testing, the following can work normally, system How does arraycopy work?
* int[] arr = {1, 2, 3, 4, 5};
* System.arraycopy(arr, 0, arr, 1, 4);//Copying to the same array with intersecting ranges
* System.out.println(Arrays.toString(arr));// [1, 1, 2, 3, 4]
* // [789 12] Self copy. It's OK to copy the three elements on the left [78, 789]
*/
System.arraycopy(arr, left, arr, right + 1 - leftRemain, leftRemain);
System.arraycopy(tmp, 0, arr, left, i);
return smallSum;
}
if (arr[left] < arr[p2]) { // Produce small sum
smallSum += (right - p2 + 1) * arr[left];
tmp[i] = arr[left++];
} else { // You must copy the number of right groups when they are equal, because you don't know how many right groups are larger than the current number
tmp[i] = arr[p2++];
}
}
System.arraycopy(tmp, 0, arr, left, tmp.length);
return smallSum;
}
Reverse order pair
In an array, if the number on the left is larger than the number on the right, the two numbers form an inverse pair. Print all inverse pairs, or find the number of inverse pairs?
[3,2,4,5,0] 5 pairs
32，30
20，
40，
50
Quick sort
Quick sort is a sort algorithm of divide and conquer. It will find an element and divide the array into two sub arrays. All elements on the left are not greater than this element and all elements on the right are not less than this element. The two parts will be sorted independently. When two subarrays are ordered, the whole array is naturally ordered.
Strategy of splitting array: arbitrarily select arr[lo] as the splitting element, scan the array from both ends of the array, and exchange all elements that do not meet the conditions of "the left element is not greater than arr[lo]" and "the right element is not less than arr[lo]". When two pointers meet, you only need to exchange arr[lo] with the rightmost element arr[j] of the left sub array and return j.
Dutch flag issue:
1. Given an array arr and a number num, please put the number less than or equal to num on the left of the array and the number greater than num on the right. Space complexity O(1) and time complexity O(N) are required
Solution: p1 points to the first element, p2 points to the last element, and p1 moves to p2. If the number pointed to by p1 is greater than num, the number exchanges with the number of p2, and p1 does not move. If it is less than or equal to, p1 moves one to the right until p1 > p2
2. Given an array arr and a number num, please put the number less than num on the left of the array, the number equal to num in the middle, and the number greater than num on the right. Space complexity O(1) and time complexity O(N) are required
Solution: p0, p1, points to the first element, p2 points to the last, and p1 moves to p2. If p1 points to an element less than num, it is exchanged with p0, p0++, p1 + +. If it is equal to p1, it moves. If it is greater than, it is exchanged with p2, p2--
heap
1. Heap structure is a complete binary tree structure realized by array
2. In a complete binary tree, if the maximum value of each subtree is at the top, it is a large root heap
3. In a complete binary tree, if the minimum value of each subtree is at the top, it is a small root heap
4. heapInsert and heapify operations of heap structure
5. Increase and decrease of reactor structure
6. The priority queue structure is the heap structure
Heap sort
Binary pile is Complete binary tree Or an approximately complete binary tree.
Binary heap the left and right subtrees of each node are a binary heap.
When the key value of the parent node is always greater than or equal to the key value of any child node, it is "maximum heap". It is "minimum heap" when the key value of the parent node is always less than or equal to the key value of any child node.
The idea of binary heap sorting: traverse the unordered array, put each number in the array into the binary heap, and then pop up the top element of the heap until it is empty.
Add element to binary heap: you can add a new element to the last leaf node and float up gradually compared with its parent node, that is, swim() method
Pop up the top element of binary heap: after obtaining the top element, replace the top element with the last leaf node of binary heap, and sink the new top element to the appropriate position, that is, sink() method.
Use array to represent binary heap: because binary heap is a complete binary tree, it can be stored in array by sequence traversal, where arr[0] is the top element of heap. For any arr[i], its parent node is arr[(i-1)/2], its left and right child nodes are arr[2 * i + 1], arr[2 * i + 2]
Binary heap depth is log(n)
Time complexity O(nlogn)
Spatial complexity O(n)
Local minimum
In an array, any number is not equal to the adjacent number. If this number is smaller than the numbers on both sides, then this number is the local minimum. The numbers on both sides only need to judge the adjacent number
If position 0 is larger than position 1 and position n-1 is larger than position n-2, there must be a local minimum from position 0 to position n-1, which can be proved by drawing a broken line graph
Find local minimum: first judge the two ends. If not, go to the middle point M. if M is not a local minimum, there must be m-1 or m+1 smaller than M. if m-1 is smaller than m, there must be a local minimum from 0 to m-1, and so on.
Logarithm
1. There is a method you want to measure a;
2. Implement an absolutely correct method with poor complexity b;
3. Implement a random sample generator;
4. The method of implementing comparison algorithms a and b;
5. Compare method a and method b several times to verify whether method a is correct;
6. If there is a sample that makes the comparison error, print which method of sample analysis is wrong;
7. When the number of samples is large, the comparison test is still correct, and it can be determined that method a is correct.
Find the midpoint
Method 1: (l+r)/2 addition may overflow
Mode 2: L + ((R-L) > > 1) shift one bit to the right is equivalent to dividing by 2
master formula
The recursive behavior conforms to such a formula. As long as the sub scale meets the same scale (that is, the sub problem is cut in half every time, or 1 / 3, 1 / 5), the master formula can be used to solve the time complexity
T(N) = a*T(N/b) + O(N^d)
N: Data volume of parent problem
T(N/b): the scale of the subproblem, if it is equal
a: The number of sub problem calls, if the sub problem size is the same
O(N^d): the time complexity of the remaining processes except the subproblem
// Find the maximum value of the array
public static int process(int[] arr, int l, int r) {
if(l == r) return arr[l];
int mid = l + ((r - l) >> 1);
int lMax = process(arr, l, mid);
int rMax = process(arr, mid, r);
return Math.max(lMax, rMax);
}
// Parent problem data quantity N
// Called the subproblem twice, so a=2
// Every time the subproblem is cut in half, so b=2, the scale of subproblem is N/2,
// d=0, time complexity of other processes is O(1)
// Log (B, a) = = log (2,2) = = 1 > D, so the time complexity is O(N)
After the three coefficients a, B and D are determined, the time complexity of recursive behavior can be obtained according to the following three cases
- log(b,a) < d -> O(N^d)
- log(b,a) = d -> O(N^d*log(N))
- log(b,a) > d -> O(N^log(b,a))