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

This article mainly explains "what are the skills of the data structure in the web algorithm". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what are the skills of the data structure in the web algorithm".

Tip 1: minimum / maximum heap for the "K minimum / maximum element" problem

Problem: given a list of numbers, use the heap data structure to find the third smallest element:

[4, 20, 16, 10, 10, 0, 47, …]

When a question is asked in the form of "find the K smallest element in the list", it is natural to use the minimum heap to propose a solution because of the word "minimum" in the problem statement. Here is a simple solution:

Build the minimum heap of a given list and call extractMin () k times. The time complexity of this solution is O (n + kLogn), which consumes extra memory of O (n).

To optimize memory and time complexity, here is a better solution:

Build the maximum heap from the first k elements of the array

For each remaining element, compare the element to the root of the largest heap. If it is less than the root, replace the root with the element and call heapify ().

After completing the second step, the root of the heap will be the k smallest element.

Time complexity: O (k + (nMuk) Logk)

Use the maximum heap for the K smallest problem.

Use the minimum heap for the K biggest problem.

Note: there are different solutions to this problem, using fast selection algorithms, median, and so on. Heaps are chosen because they are easier to understand and visualize.

Tip 2: use index mapping

Index mapping is a technique used many times in technical interviews to save search time at the cost of using more memory.

Problem: use O (1) search time to realize the minimum heap data structure.

Start with simplicity. Only focus on the "search" section, the minimum heap has been implemented.

This is the smallest heap, which is represented as the following array:

[0, 4, 16, 10, 20, 47]

Want to find the subscript for a given node, say 10.

Do a linear search on the array until you find element 10, which takes O (n) time. But it takes O (1) time. Maybe it's because you want to update the value of this node, and you're doing a lot of updates, so you don't want to spend time looking for elements.

Obviously, it is impossible to magically have O (1) search time unless some resources are sacrificed. We can keep the index of each node in the hash map. Whenever you update the heap, you need to update the index on this hash map.

For the heap above [0re4, 16, 10, 20, 47], the index maps as follows:

{0:0, 4:1, 16:2 10:3, 20:4 47:5}

Now we can find out the position of node 10 in O (1) time. If you change the order of the elements in the heap, their relative indexes in the index mapping data structure are also updated.

Note: other data structures can be used, such as index-mapped trees.

Follow-up question: can I use the same technique for pointers / references?

Tip 3: delete an element from an unordered array in O (1) time

Problem: remove the element "4" from [10pd4, 56pcg0p8p1] in O (1) time.

When you delete a specific element from the array, all subsequent elements move to the left, which takes O (n) time. This is perfect, and it is the most commonly used technique, which retains the order of the array.

But if you don't care about the order of the elements, there is an easier way to "delete" in O (1) time: replace the element to be deleted with the last element of the array. Then reduce the array size by 1.

For the above example, delete "4" and write:

[10, 1, 56, 0, 8, 1] # replace "4" [10, 1, 56, 0, 8] # with the last element "1" to reduce the array size 1.

Follow-up question: what if you care about the order? Can it be saved in different data structures?

Tip 4: understand the basic principles of binary search

Binary search is not just about finding an element in an ordered array, it has more power. Once you understand its basic principles, you will be impressed by the ability to solve problems with it.

Question:

Farmer John built a new barn with N corral. Given an integer array An of size N, where each element in the array represents the position of the corral and the integer B represents the number of cows. His cows don't like the layout of the barn, which makes them very aggressive in the warehouse. In order to prevent the cows from hurting each other, John wants to assign the cows to the corral.

John wants to make the minimum distance between them as large as possible. So what is the maximum value of this minimum distance? Can we solve this problem with binary search?

Tip 5: bit operation

Bit manipulation is a useful technique for optimizing code (mainly memory). It can be used for a variety of problems, and you can use shift, and / or XOR / non-operations.

Here are the bit operations you must understand:

X ^ x = 0 x ^ 0 = x x | 0 = x x & 1 = xGet i th bit on num: (num & (1)

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.