For algorithms, strange and mysterious, but it is a necessary way to grow up.

Have countless times to find all kinds of information, seeking all kinds of so-called seven days to fix the algorithm, but the results are endless and return.

In other words, I’m an Android guy, and I sometimes dismiss the idea that 7 days makes you an Android juggler. Without long-term accumulation, where can you come from? Once toss over things for a long time, now easy a batch, to put it bluntly, or a long time, write more.

A person, unavoidably will walk into all kinds of misunderstanding. Having experienced PUA in the workplace, I realized that THERE was nothing else I could do for myself.

It’s the same chicken quote:

  • Just do it now.

To you and me in front of the screen.

For the algorithm, will take violence Study method, diligent can compensate clumsy! Learn and practice.

Individual is an algorithm idiot, as far as possible to improve each step, inadequate, welcome to slings ~

Welcome you big shot ~

Attached is GitHub address:

  • Github.com/HLQ-Struggl…

349. Intersection of two arrays

Given two arrays, write a function to calculate their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2]Copy the code

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Copy the code

Description:

  • Each element in the output must be unique.
  • We can ignore the order of the output.

Review of intersection concepts

For example, the overlap between A and B is intersection C.

For example, A and B are as follows:

  • A: 1, 3, 4, 5, 6
  • B: Two, three, three, four

The overlapped parts are as follows:

  • 3, 4,

So we get intersection C is equal to 3, 4.

The idea of intersection, in plain English, is that you have something and I have something, it’s intersection. Here the derived union is, yours plus mine, minus the duplicates, that’s the union.

Set + contains

The general idea is as follows:

  • For basic verification of input data, there is no more explanation here;
  • Filter the first array with Set uniqueness;
  • Compare the first filtered array with the second array. If the first filtered array is included, the Result is overlapped.
  • Traverse Reslut, and assign return array

The code is as follows:

class Solution {
    fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
        if(nums1.isEmpty() || nums2.isEmpty()){
            return IntArray(0)
        }
        var tempSet = hashSetOf<Int>()
        var resultSet = hashSetOf<Int>()
        for(num1 in nums1){
            tempSet.add(num1)
        }
        for (num2 in nums2){
            if(tempSet.contains(num2)){
                resultSet.add(num2)
            }
        }
        var resultIntArray = IntArray(resultSet.size)
        var index = 0
        for(resultNum in resultSet){
            resultIntArray[index++] = resultNum
        }
        return resultIntArray
    }
}
Copy the code

Consumption:

1. Kotlin Intersect ()

class Solution {
    fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
        if(nums1.isEmpty() || nums2.isEmpty()){
            return IntArray(0)
        }
        return nums1.intersect(nums2.asList()).toIntArray()
    }
}
Copy the code

Consumption:

Compared with the original first scheme, the execution time and memory consumption are increased a lot. After comparing the code, this method adds two forwarding List operations.

Third, continue to optimize the second

As mentioned above, there is a certain amount of consumption due to multiple iterations of the List, so what if I create less and simplify the code?

class Solution {
    fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
        if(nums1.isEmpty() || nums2.isEmpty()){
            return IntArray(0)
        }
        return nums1.intersect(nums2.asList()).toIntArray()
    }
}
Copy the code

Consumption:

That’s a little awkward.

4, Learn to sort + double pointer

Reference:

  • Resolve intersection of two arrays with Multiple Solutions [Persian Leopard]

First attach the code section:

class Solution { fun intersection(nums1: IntArray, nums2: IntArray): IntArray { if(nums1.isEmpty() || nums2.isEmpty()){ return IntArray(0) } var i = 0 var j = 0 var index = 0 var resultSet = hashSetOf<Int>(); While (I < nums1.size &&j < nums2.size){// iF (I < nums1.size &&j < nums2.size){ If (nums1[I] == nums2[j]){resultset.add (nums1[I]) I ++ j++}else if(nums1[I] < nums2[j]){I ++}else if(nums1[I] < nums2[j]){I ++}else if(nums1[I] > nums2[j]){ j++ } } var resultArray = IntArray(resultSet.size) for (resultNum in resultSet){ resultArray[index++] = resultNum } return resultArray } }Copy the code

Degree of consumption:

End

Purely from the above results, the first pass through Set + contains is the most efficient. On the double pointer piece, although it is a long time to draw the graph, quickly still understand the meaning of almost.

It seems to be vaguely aware of the importance of algorithms, in other words, the idea of algorithms.

But overall pretty happy, at least it is the first time in life to get it done ~

Welcome big guy to sling ~

The way ahead is so long without ending, yet high and low I’ll search with my will unbending.

The resources

  • Intersection of two arrays in Xiaohao algorithm (350)
  • LeetCode 349. Intersection of two arrays
  • LeetCode problem 349: Intersection of two arrays