Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of "Java array high-frequency test site case analysis". The editor shows you the operation process through the actual case. The operation method is simple, fast and practical. I hope this article "Java array high-frequency test site case analysis" can help you solve the problem.

1. The theoretical basis of array

An array is a collection of the same type of data stored in continuous memory space, which can be obtained by subscript index.

Take a chestnut (character array) ~

You can see:

1. The subscript of the array starts with 0

2. The address of the array in memory is continuous.

So when deleting an element, it can only be done as an override.

For example, to delete the element with subscript 2 ~, you need to move the element after 2 to the previous one in turn, overwriting the element to be deleted.

So to delete an element is not to free up the space of the element, but to move the following element to the front, overwrite the element to be deleted, and then subtract 1 from the length of the array to get a seemingly new array.

In java, two-dimensional arrays are stored as follows:

2. Common test sites 1. Binary search

Force buckle topic link: binary search

The premise of this topic is an ordered array, because once there are repeating elements, the element subscript returned by binary search may not be unique, which are prerequisites for using dichotomy.

The idea of binary search is:

Under the premise that the array is ordered (assuming ascending order), if the value in the middle of the array is greater than the value to be found, then the element to be searched cannot be in the second half, because the value in the second half is greater than the middle value, so through the first comparison, the range can be reduced by half, which is the same, that is, the time complexity is reduced to O (logN), and the efficiency is greatly improved. When the time complexity of finding elements in the question is O (logN), first think about whether two points can be used.

Class Solution {public int search (int [] nums, int target) {/ / avoid cyclic operation if (target) multiple times when target is less than nums [0] nums [nums.length-1]

Nums [nums.length-1]) {return-1;} int left = 0, right = nums.length-1; while (left > 1); if (nums [mid] = = target) return mid; else if (nums [mid]

Target) right = mid-1;} return-1;}} 2. Remove element

Some students may have said, superfluous elements, just delete it? But to know that the elements of the array are contiguous in the memory address, you can't delete an element in the array alone, you can only overwrite it.

For example, what should I do if I give you an array and a Val value and ask to delete the elements in the array that are equal to the Val value?

Idea 1: violence method

We can use two for loops, and when we traverse to an element equal to the value of vale, we move the following element forward as a whole to overwrite the element to be deleted, but this is obviously too time-consuming.

Class Solution {public int removeElement (int [] nums, int val) {int size = nums.length; for (int I = 0; I < size;i++) {if (nums [I] = = val) {/ / find the elements that need to be removed, then move the back of the array forward one bit for (int j = I + 1; j < size) Size--; +) {nums [j-1] = nums [j];} iMeltel; / / because all the values after the subscript I move forward one bit, so I also moves forward one bit size--;} return size;}}.

Train of thought 2: double pointer method

Set a fast and slow pointer, slow fast, both go together, when the slow pointer meets the element to be deleted, waiting to be deleted (overwritten); when the fast pointer goes to the element to be left behind, the element of the fast pointer is assigned to the slow pointer, and then the two pointers go backward at the same time until the fast pointer traverses the entire array.

It can be understood like this: define the new length of the array newLength, starting from 0, define a fast pointer traversal array fast, when fast goes to the element to be left behind, it means that the element should be added to the new array (that is, it should be added to the newLength subscript, which is equivalent to the part of the array before newLength is regarded as the new array to be returned, which is equivalent to inserting elements into the new array).

Class Solution {public int removeElement (int [] nums, int val) {int fast = 0 if / define a fast pointer traversal array int newLength = 0 nums.length / define a new array length while (fast < nums.length) {if (nums [fast]! = val) {nums [newLength++] = nums [fast];} fast++ } return newLength;}}

Recommend the power to buckle the topic

1. Delete duplicates in a sorted array

two。 Move zero

3. Compare strings with backspace

4. Square of ordered array

Many of the test sites of other common arrays are based on these two points, nothing more than adding, deleting, changing and querying the array, mastering the search and deletion of the array, and then you can start doing exercises.

This is the end of the content of "case Analysis of High Frequency Test sites in Java Array". Thank you for your reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.