Basic properties of arrays
Array is the simplest data structure.
Array is used to store a series of data of the same type. Data is stored continuously and memory is allocated at one time.
Insert and delete in the middle of the array. All subsequent data must be moved each time to maintain continuity. The time complexity is O(N).
Array index
Array supports fast access to data through index. An array with length of N starts with 0 and ends with N-1.
Array elements can be accessed by adding an index to the array name. The index of the element is placed in square brackets, following the array name.
Array expansion
Array memory space is allocated at one time. During capacity expansion, apply for a larger memory space, and then copy the data to the new memory space. The time complexity is O(N).
Array traversal
for (int i = 0; i < arr.length; i++) {
//Array element operation using arr[i]
}
Array statistics
How to count the number of occurrences of elements in an array?
If the given array elements are all non negative numbers, we can borrow additional auxiliary arrays to achieve the statistical purpose of counting the number of elements in the array.
for (int i = 0; i < nums.length; i++) {
help[nums[i]]++;
}
How to quickly specify the position of a given element in an array? xx position on the left? xx position on the right?
For elements appearing at the xx position on the left and xx position on the right of the array, the auxiliary array is still used.
Using left [], right [], record the number of positions from the left and the number of positions on the right of the array respectively;
for (int i = 0; i < nums.length; i++) {
left[nums[i]] = i;
}
for (int i = nums.length - 1; i >= 0 ; i--) {
right[nums[i]] = nums.length - 1 - i;
}
How to determine whether array elements are duplicate or missing?
If the array is a positive number of 1~n, you can judge by modifying the status of the original array;
The first time you access an element, invert the element to a negative number;
Access the element for the second time and judge that the element status is negative, then this element is a duplicate element;
After all States are modified, traverse the array. When it is judged that the element is a positive number, then this position i is the missing element!
Force buckle [645. Wrong set]
The set s contains integers from 1 to n.
Unfortunately, due to data errors, a number in the set is copied into the value of another number in the set, resulting in the loss of a number in the set and the repetition of a number.
Given an array nums, it represents the result of the error in set S.
Please find the repeated integers, find the missing integers and return them in the form of array.
Specific description
Problem solving idea 1: auxiliary array
Traverse the original array and use the auxiliary array help [], to store the number of occurrences of each number.
For example, help[nums[i]] stores the number of occurrences of the number I.
Traversal auxiliary array
The number of repetitions is greater than 1
The number of times equal to 0 is the missing number
Complexity analysis
Time complexity: O(n). ergodic nums It takes time O(n)，It takes time to check each number O(n). Space complexity: O(n). array arr Up to 1 to n common n The number of occurrences of a number.
Animation simulation
Example
//Auxiliary array
public static int[] findErrorNums1(int[] nums) {
//Auxiliary array, the data is from {1~N, so the length is + 1
int[] help = new int[nums.length + 1];
//Modify the auxiliary array according to nums ， and count the number of occurrences of nums ， elements
for (int num : nums) {
help[num]++;
}
//Traversal auxiliary array
//If the number of times is greater than 1, it is the number of repetitions
//The number of times equal to 0 is the missing number
int[] res = new int[2];
for (int i = 1; i < help.length; i++) {
if (help[i] > 1) {
res[0] = i;
}
if (help[i] == 0) {
res[1] = i;
}
}
return res;
}
Solution 2: modify the status of the original array elements
Given the array nums [], the stored numbers are positive numbers and between 1 and n.
Traverse nums [], find nums[|i |] according to i, and if it is the first time to access nums [∣ i ∣], reverse it to a negative number.
When it is encountered again, the query has become a negative number, so this number is the repetition number.
After completing the traversal, all the numbers corresponding to the index are negative, and only the index corresponding to the missing number j is still positive.
Traverse num [] again and find the position + 1 of the positive element in the array, which is the missing number.
Complexity analysis
Time complexity: O(n). ergodic nums It takes time O(n)，It takes time to check each number O(n). Space complexity: O(1). Use constant extra space.
Animation simulation
Example
//Changes the number encountered for the first time to a negative number
//When the query is encountered again, it has become a negative number, so this number is the repetition number
public static int[] findErrorNums2(int[] nums) {
// 1 2 4 3 3 3 4
// a[0] -1 2 4 3 3 3 4
// a[1] -1 -2 4 3 3 3 4
// a[2] -1 -2 4 -3 3 3 4
int[] res = new int[2];
for (int num : nums) {
if (nums[Math.abs(num) - 1] < 0) {
//Number of repetitions
res[0] = Math.abs(num);
} else {
//The element is accessed for the first time and set to 0
nums[Math.abs(num) - 1] *= -1;
}
}
//Traverse the array to find the position of the positive element in the array, that is, the missing number
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
res[1] = i + 1;
}
}
return res;
}
Short talk long talk
Learning algorithms, I don't know where to start? What to learn first? At what stage should I brush what questions?
According to the structural sorting of force buckle topic categories, brush questions from low-level to high-level, graphic algorithm (updating...), interested children's shoes, welcome to start zero basic force buckle from Xiaobai and make common progress!
Interested search: jiongmefeishi (or search: jiongmefeishi)
Public number reply: 678, get the sorting order, and follow up content will be renewed continuously. Interested buddy will be free to pick up official account.
In addition, as for the classification, please don't ask me about the name of the last category. Qiji Yinqiao is a commendatory word, which means novel skills and works.
Problems, classification of problems, recommended brushing sequence and solution of problems in Li Kou cultivation system
At present, it is tentatively divided into four stages:
Algorithm low level beginner level chapter--Martial forging body Algorithm intermediate advanced level--Wu Huanglian's heart Higher order reinforcement of algorithm--The soul of Emperor Wu Algorithmic tricks--Battle Secret Code Forgive me for having a fairy dream...
Missing content, trying to sort it out