Using hashes to solve problems

In the solution of the problem of force deduction , We can often see the shadow of hash . today , Let's explore the algorithm of hash .

Catalog

One . principle

Two . solve the problem

1. Sort

2. Cross reference search between data

  3、 ... and . Advantages and disadvantages

One . principle

Generally speaking , Hash is to open up a string of spaces , Give them different marks , Then put the data to be solved into the designated space according to the corresponding marks . Just search whether there is data in the space , You can use the corresponding data according to the spatial markers .

For example, there is a string of numbers ：3 5 1 6 0 4 2 7 1  3 8 8 1 0 5

The maximum is 8, The minimum is 0, We can open up 9 Space , Take the corresponding number in the data as the subscript to find the specified space , If you find it, add one to the space value .

First, the initialization space values are 0.

Then use the data as a subscript to retrieve the corresponding space , Add one to the retrieved space value .

With 3 For example , Then the subscript is 3 Space value of plus one .

Retrieve all data in turn .

Two . solve the problem

The hash table produced in this way can solve many problems .

1. Sort

Through the value of space, we can know whether there is such data in the sorting , How much is this data .

For example, the subscript in the above figure is 0 The space value of is 2, It means that the value is 0 There are a total of 2 individual .

therefore , For sorting , We just need to determine the quantity against the spatial value to print the subscripts in turn .

2. Cross reference search between data

Some problems may require us to search the data against each other . Simple data is ok , If the data is complex or very troublesome in comparison , It is very likely to make the problem extremely difficult to solve . At this time , Using hash table to solve problems may greatly reduce the difficulty of solving problems .

Here we use questions as examples , Specific ideas Xiaobian has written a blog for you ： Try to solve the problem - Word substitution

If you don't understand anything, you can write a private letter at any time , I will try my best to answer for you .

Of course , Here is another similar topic for you ：30. Concatenate the substrings of all words - Power button （LeetCode）

  The specific solution ideas will be updated in the blog later .

  3、 ... and . Advantages and disadvantages

The biggest advantage of hash table is intuitive and Fast .

The time complexity of hashing is usually O(n).

Especially for sorting ,O(n) The time complexity of is terrible . Because there are only O(n * log^n).

But the corresponding , The biggest drawback of hashing is High spatial complexity . It depends on the range size of the data .

therefore , Hash is a kind of Use space for time The algorithm of .

Life is too short , Don't do something that no one wants at all .——Ash Maurya

If there is a mistake , Please correct