An array of frequent interview algorithms

This is the 8th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Hello everyone, I am a senior programmer ~

Today to bring you a detailed analysis of the interview high-frequency algorithm array, the full text contains 19 dachang written interview algorithm real questions, at one stroke to take the array of knowledge, so that the algorithm is not a stumbling block to enter dachang.

If you like it, be sure to follow it

This article is a bit long, I have made a PDF version of this article with table of contents, to get the PDF version of this article, please send me a private message.

The full text overview

The basics of arrays

The definition and characteristics of arrays

An array is a linear table data structure that stores the same type of data in contiguous memory space.

Arrays have the following characteristics.

The index of the array starts at 0.
Contiguous memory space and the same data type.

Because the memory space of an array is contiguous, we can “randomly access” the elements in the array. But there are pros and cons. If you want to insert or delete an element in an array, in order to keep the memory space of the array contiguous, you have to move other elements.

For example, to delete an element with subscript 2, you need to move all elements after it forward. As shown in the figure:

There are clever ways to solve the problem

dichotomy

If a given array is ordered, we need to consider whether we can solve it using dichotomy (dichotomy has O(logn) time). Dichotomy in the interview is often tested in the interview knowledge points, suggest that we must exercise the ability to tear dichotomy hand.

Double pointer method

We can do two for loops in one for loop with one fast pointer and one slow pointer. For example, when we need to enumerate two elements in an array, if we find that the second element decreases as the first element increments, we can use the two-pointer approach to reduce the time complexity of the enumeration from O(N^2) to O(N).

The sliding window

As the name suggests, a sliding window is one that slides over a sequence. The window size has fixed length, also has variable length. For example, given an array [2,2,3,4,8,99,3] with a window size of 3, finding the sum of the elements of each window is a fixed-size window problem. Finding the longest continuous subarray of the array [2,2,3,4,8,99,3] is a window variable problem. Using sliding Windows, we can reduce the time complexity of the algorithm.

When using sliding Windows to solve problems, it is mainly necessary to know what conditions to move the starting position of the window, and when to dynamically expand the window, so as to solve the problem.

Hash table method

If we need to find the existence of an element in an array, we can use hash table, which can reduce the time complexity of finding elements from O(n) to O(1).

The sum of two Numbers

Problem description

LeetCode 1. Sum of two numbers

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.

Example 1:

Enter nums = [2,7,11,15], target = 9

Output: [0, 1]

Because nums[0] + nums[1] == 9, return [0, 1]

To analyze problems

The simplest and most intuitive idea to take this problem is to look for target-x for each element x in the array.

def twoSum(nums, target): n = len(nums) for i in range(n): For j in range(I + 1, n): if nums[I] + nums[j] == target: return [i, j] return []Copy the code

We can clearly see that the time of this algorithm is O(n^2). So how can we reduce time complexity? Notice that the complexity of this algorithm is high because we need to go through the array to find the target-x element, so we need to optimize this part. We can use a hash table to reduce the time complexity of finding element target-x from O(n) to O(1).

For each element x, we first query the hash table to see if target-x exists. If so, we return the matched result directly. If not, we insert x into the hash table.

Tips: Instead of using a hash table, we use a dictionary to overwrite the inserted element when it is repeated, thus keeping the lookup time O(1). And why we can override that? Because they’re asking us to find two numbers that add up to target, and when we have two elements that repeat, we think they’re equivalent, so we just keep one of them.

def twoSum(nums, target): hash_table = dict() for i, num in enumerate(nums): if hash_table.__contains__(target-num): return [hash_table[target - num], I] hash_table[nums[I]] = I return [] nums = [2,7,11,15]Copy the code

We can see that the time complexity of this algorithm is O(n), and the space complexity is also O(n).

To optimize the

When we need to enumerate two elements in an array, if we find that the second element decreases as the first element increases, we can use the two-pointer method to reduce the time complexity of the enumeration from O(N^2) to O(N). So we can use the double pointer method to solve. Sum =nums[left]+nums[right]; sum=nums[left]+nums[right];

If sum>target, the pointer moves to the left and decreases the value of sum, i.e., right=right-1.
If sum
If sum=target, return directly.

Let’s look at the implementation of the code.

def twoSum(nums, target):
    nums=sorted(nums)
    left=0
    right=len(nums)-1
    while left < right:
        sum=nums[left]+nums[right]
        if sum>target:
            right=right-1
        elif sum<target:
            left=left+1
        else:
            return [left,right]
Copy the code

Sorted using sorted, time complexity is O(nlogn), space complexity is O(n). So the time complexity of this algorithm is O(nlogn), and the space complexity is O(n).

Longest non-repeating subarray

Problem description

LeetCode3. The oldest string without repeating characters

Given an array arr, return the length of the longest subarray of non-repeating elements of arR. Non-repeating means that all numbers are different. Subarrays are contiguous. For example, subarrays of [1,3,5,7,9] have [1,3], [3,5,7], etc., but [1,3,7] is not a subarray.

The sample

Input:,2,3,4,8,99,3 [2]

Return value: 5

[2,3,4,8,99] is the oldest array

To analyze problems

Before we get started, let’s talk about sliding Windows. As the name suggests, a sliding window is one that slides over a sequence. So let’s say we have a sequence called ABcabcbb, and we’ve defined a window of fixed size 3 to slide around the sequence.

In practical use, we use sliding Windows are variable length.

We can use the double pointer to maintain the beginning and end of the window, and move the left and right Pointers to change the size of the window and slide the window.

Let’s take a look at the problem, and they’re asking us to find the longest subarray of non-repeating elements, and if we can find all the subarrays of non-repeating elements, we’ll just take the longest one. So let’s see how we can solve this. We just need to maintain a window that slides through the array.

2 is not in the window at the beginning, so expand the window.

The next element, 2, appears in the window, so we remove all of the elements that have appeared and the elements to the left of them from the window, 2.

The next elements 3, 4, 8, and 99 don’t appear in the window, so we add them all to the window.

The next element 3 appears in the window, so we remove that element and the element to the left, 2,3.

Let’s take a look at how the code works.

Window = set() n = len(s) max_len = 0 for I in range(n): While s[I] in window: Add (s[I]) max_len = Max (len(window),max_len) return max_lenCopy the code

The algorithm’s time complexity is O(n).

Merges two ordered arrays

Problem description

LeetCode 88. Merge two ordered arrays

You are given two non-descending arrays of integers, nums1 and nums2, and two integers, m and n, representing the number of elements in nums1 and nums2, respectively. Please merge nums2 into nums1 so that the merged array is also in non-descending order.

Note: Finally, the merged array should not be returned by the function, but stored in the array nums1. To deal with this, nums1 has an initial length of m + n, where the first m elements represent the elements that should be combined and the last n elements are 0 and should be ignored. Nums2 has a length of n.

Example:

Input: nums1 = [1,2,3,0,0], m = 3, nums2 = [2,5,6], n = 3

Output:,2,2,3,5,6 [1]

Explanation: need to merge [1,2,3] and [2,5,6]. The combined result is [1,2,2,3,5,6].

### Analyze the problem

The simplest and most violent way is to put nums2 in the last n positions of nums1 and sort nums1 directly. We will not repeat it here.

def merge(nums1, m, nums2, n): Nums1 [m:] = nums2 nums1.sort() nums2 = [1,2,3,0,0,0] m = 3 nums2 = [2,5,6] n = 3 print(nums1,m,n)Copy the code

So given that these two arrays are ordered, why don’t we use this condition to optimize our code. So, we can use two Pointers, P1 and p2, to point to the start of each array, compare the size, place the smaller one in the result, and move the pointer back until everything is sorted.

Let’s look at the implementation of the code.

Nums2 def merge (nums1, m, n) : # sorted the temporary storage element sorted = [] (p1, p2 = 0, 0 # not traverse the array while p1 and p2 < m < n: Append (nums1[p2]) p1 += 1 else: sorted. Append (nums2[p2]) p2 += 1 if p1 == m: for x in nums2[p2:]: sorted.append(x) else: for x in nums1[p1:m]: Sorted. Append (x) nums1[:] = sorted nums1 = [1,2,3,0,0,0] m = 3 nums2 = [2,5,6] n = 3Copy the code

We know that the time complexity here is order m plus n, and the space complexity is order m plus n.

To optimize the

With the two-pointer method, we iterate through the array from front to back, and if we use nums1 directly to store the merge result, the elements in nums1 may be overwritten before fetching. So we introduced a temporary variable called sorted to store it. Is there any way to avoid overwriting elements in nums1? If going backwards is not possible, can we go backwards? Since the back half of NUMs1 is empty and can be overwritten directly without affecting the result, the reverse two-pointer method is introduced here.

Let’s look at the code implementation.

Nums2 def merge (nums1, m, n) : # to the end of the array element p1 p2 = m - 1 = n - 1 tail = m + n - 1 while p1 or p2 > = 0 > = 0: If p1 == -1: nums1[tail] = nums2[p2] p2 -= 1 Elif nums1[p1] = nums2[p2]: nums1[tail] = nums1[p1] p1 -= 1 else: nums1[tail] = nums1[p1] p1 -= 1 nums1[tail] = nums2[p2] p2 -= 1 tail -= 1Copy the code

The time complexity of the algorithm is O(m+n) and the space complexity is O(1).

Spiral matrix

Problem description

LeetCode 54. Spiral matrices

You are given a matrix matrix with m rows and n columns. Please return all elements in the matrix in clockwise spiral order.

Example:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]

Output:,2,3,6,9,8,7,4,5 [1]

To analyze problems

The instructions are to output in a clockwise spiral order, from left to right, then top to bottom, then right to left, then bottom to top, and so on, until all the elements are iterated. In traversal, the most important thing is to keep track of which elements have been accessed, and if one element has been accessed, we need to adjust the direction clockwise.

The most intuitive idea to determine whether an element has been accessed is to declare a matrix of the same size as the matrix to identify whether the elements in the matrix have been accessed.

Let’s see how the code works.

Def spiralOrder(matrix): if not matrix or not matrix[0]: return [] rows=len(matrix) columns=len(matrix[0]) visited = [[False for _ in range(columns)] for _ in range(rows)] Count =rows*columns result=[0]*count # Directions = [[0, 1], [1, 0], [0, -1], [-1, 0]] Row, column = 0, DirectionIndex = 0 for I in range(count): Result [I] = matrix[row][column] # visit [row][column] = True NextColumn = row + Directions [directionIndex][0], Column + Directions [directionIndex][1] If not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]): directionIndex = (directionIndex + 1) % 4 row += directions[directionIndex][0] column += directions[directionIndex][1] return resultCopy the code

Since a matrix of the same size as the original matrix is created to indicate whether elements have been accessed, the spatial complexity of the algorithm is O(Mn). The elements in the matrix are traversed once, so the time complexity of the algorithm is also O(Mn).

To optimize the

So is there a way to optimize the spatial complexity of the algorithm? That is, we don’t have to create a new space to store whether or not the elements in the matrix have been accessed.

In fact, we can constantly change the boundary conditions in the traversal process. When the first row of the matrix is accessed, the upper boundary needs to be +1; If the last column element has been accessed, the right margin needs to be operated -1; If the element in the last row has been accessed, the lower boundary needs to be operated -1; If the first column is accessed, the +1 operation is required; And so on until the traversal is complete.

Def spiralOrder(matrix): if not matrix or not matrix[0]: Return [] rows = len(matrix) columns = len(matrix[0]) result=[] # Left =0 right=columns-1 up=0 down=rows-1 while True: # for I in range(left,right+1): Result. Append (matrix[up][I]) # append(matrix[up][I]) # append(matrix[up][I]) # append(matrix[up][I]) # append(matrix[up][I]) # append(matrix[up][I]) # Result. Append (matrix[I][right]) # right=right-1 Break # from right to left for I in range(right,left-1,-1): result.append(matrix[down][I]) # down=down-1 if down<up: For I in range(down,up-1,-1): result.append(matrix[I][left]) left=left+1 if left>right: break return resultCopy the code

The time complexity of the algorithm is O(m*n) and the space complexity is O(1).

Three numbers neutralized by 0 in the array

Problem description

LeetCode refers to Offer II 007. The three numbers in the middle of the array are 0

Given an array nums containing n integers, determine whether there are three elements a, B, and c in nums such that a + b + c = 0. Find all triples that sum to 0 and are not repeated.

Example:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[1, 1, 2], [1, 1]]

To analyze problems

This problem is an upgraded version of the sum of two numbers, so we can also use the two-pointer method. The three numbers how to use the double pointer method, in fact, very simple, we first fixed a number down, and then the other two numbers to use the double pointer to find not good. By convention, we first sort the array, then fix the first number, assuming nums[I], and then use the two-pointer method to find the sum of the two numbers in the array equal to -nums[I]. Because the triplet is not repeated, we need to decide to remove the repeated solution. There are two main cases of repeated solutions.

When nums[first]=nums[first-1], there is no need to repeat the solution since we have already solved for the triplet whose first element is **nums[first-1]**.
When nums[first]+nums[left]+nums[right]=0, nums[left]=nums[left+1] or nums[right]=nums[right+1], nums[left]=nums[right+1].

Let’s look at the implementation of the code.

Def threeSum(nums): n=len(nums) result=[] if n<3: return result nums=sorted(nums) print(nums) # First =nums[I] =nums[I] If I >0 and first==nums[i-1]: Continue # target=-first right=n-1 left= I +1 while left<right: if nums[left]+nums[right]==target: Result. Append ([nums[I],nums[left],nums[right]]) # While left<right and nums[left]==nums[left+1]: While left<right and nums[right]==nums[right-1]: right=right-1 left=left+1 right=right-1 elif nums[left]+nums[right]>target: right=right-1 else: Left =left+1 return result nums=[-1,0,1, 1, -1, -1] print(threeSum(nums))Copy the code

The number that occurs more than half The Times in an array

Problem description

LeetCode refers to Offer 39. A number that occurs more than half the time in the array

Given an array of length n, find a number that occurs more than half the length. For example, enter an array of length 9 [1,2,3,2,2,2,5,4,2]. Since the number 2 appears in the array five times, more than half the length of the array, 2 is printed.

Example:

Input:,2,3,2,2,2,5,4,2 [1]

Output: 2

To analyze problems

Hash table method

The easiest way to think about it is to use a hash table, to count the number of occurrences of each number, it is easy to find the superior number.

Def majorityElement(nums): def majorityElement(nums) = {} for x in nums: if x in data_count: data_count[x] = data_count[x] + 1 else: Data_count [x] = 1 max_value=0 max_key=0 value=data_count[key] if value>max_value: Max_value =value max_key=key return max_key data=[1,2,3,2,2, 5,4,2] print(majorityElement(data)Copy the code

The time complexity of this algorithm is O(n), and the space complexity is also O(n).

Sorting algorithm

If we sort the array, the midpoint of the sorted array must be the mode.

def majorityElement(nums): Nums [len(nums) // 2] data=[1,2,3,2,2, 5,4,2] print(majorityElement(data))Copy the code

Boyer-moore voting algorithm

The classic solution to this problem is the Boyer-Moore voting algorithm. The core idea of Boyer-Moore voting algorithm is that the number of votes is positive and negative offset, that is, in the case of mode, we add the number of votes +1, and in the case of non-mode, we add the number of votes -1, so the sum of all votes must be greater than 0.

We assume that the mode of the array nums is X and the length of the array is n. We can easily know that if the sum of the first a numbers in the array is 0, then the sum of the remaining n-a numbers must be greater than 0, that is, the mode of the last n-a numbers is still X.

The first element of the array is n1, the mode of the array is x, and we iterate and count the votes. When the sum of votes is 0, the mode of the remaining elements of the array must also be X, because:

When n1 is equal to x, of all the numbers that cancel out, half of them are mode x.
When n1 is not equal to x, the mode is at least 0 and at most half of all the numbers that cancel out.

So, in removing m characters, we remove at most half of the mode, so x is still mode in the remaining n-m elements. Using this feature, we can shrink the remaining array range every time we encounter a sum of votes of 0. When the traversal is complete, the number assumed in the last round is the mode.

Class Solution: def majorityElement(self, nums): # count =0 If num==x: counts=counts+1 else: counts=counts-1 return xCopy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).

Merge range

Problem description

LeetCode 56. Merge intervals

The array enjoyments is a set of intervals, where a single interval is enjoyments [I] = [Starti, endi]. You merge all overlapping ranges and return a non-overlapping array of ranges that exactly covers all of the ranges in the input.

Input: [[1,3], [2,6], [8,10], [15,18]] output: [[1,6], [8,10], [15,18]] explanation: intervals [1,3] and [2,6] overlap, merge them into [1,6]

To analyze problems

For any two intervals A and B, the relationship between them can have the following six situations.

We compare and swap these two intervals to make it true that the starting position of the first interval is less than or equal to the starting position of the second interval. In this way, we can convert these six conditions into the following three.

In this way, we order all intervals according to their left endpoints, and then we can guarantee that for any two consecutive intervals, the starting position of the first interval is less than or equal to the starting position of the second interval, so their relationship is only in the above three cases.

algorithm

For the above three cases, we can use the following algorithm to solve.

First, we use the array merged to store the final answer. Next we add the first interval to the merged array and consider each subsequent interval in sequence:

If the left endpoint of the current interval is after the right endpoint of the last interval in the array merged, which is the second case in the figure above, then they do not overlap. We can add this interval directly to the end of the merged array;
In the first and third cases above, we need to update the right endpoint of the last interval in the array merged with the right endpoint of the current interval, and set it to the larger value of the two.

Now that we can solve all three of these cases, let’s look at the code implementation.

Class Solution: def merge(enjoyments): # Enjoyments (enjoyments): X [0]) # merged = [] for interval in intervals: If merged or merged[-1] < interval[0]: merged. Append (interval) else: if merged or merged[-1] < interval[0]: merged. Merged [-1] = Max (merged[-1][1], interval[1]) return mergedCopy the code

The time complexity of the algorithm is O(nlogn), where n is the number of intervals. Excluding the sorting overhead, we only need one linear scan, so the main time cost is O*(*n logn) of sorting. The space complexity is order logn.

Finds the upper median in two sorted arrays of equal length

Problem description

LeetCode 4. Find the median of two positive ordinal groups

Given two increasing arrays arr1 and arR2, both of length N, find the upper median of all the numbers in the two arrays. Upper median: Assume that the increasing sequence length is N, which is the NTH / 2nd number.

Requirements: Time complexity O(n), space complexity O(1).

Advanced: Time complexity is O(logN), space complexity is O(1).

Example:

Input: [1,2,3,4], [3,4,5,6]

Return value: 3

Note: There are 8 numbers in total, and the upper median is the fourth smallest number, so return 3.

To analyze problems

The most intuitive idea of this problem is to merge two ordered arrays into one large ordered array using merge sort. The upper median of a large ordered array is the NTH/second digit. We can know that the time complexity of this algorithm is O(N), and the space complexity is also O(N), which obviously does not meet the space complexity of O(1) required by the question. In fact, we don’t need to merge two ordered arrays, we just need to find the location of the upper median. For a given length of N two array, we can know the digit position for N, so we maintain two Pointers, initial point to the location of the two array subscript 0 respectively, each pointer to a smaller value will back one (if a pointer has already reached the end of the array, then only need to move another array pointer), until it reaches the position of the median.

Let’s take a look at how the code works.

class Solution: def findMedianinTwoSortedAray(self , arr1 , arr2 ): P1 =p2=0 ans=0 while p1+p2<N: If arr1[p1]<=arr2[p2]: ans=arr1[p1] p1=p1+1 else: ans=arr2[p2] p2=p2+1 return ansCopy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).

The advanced

Now let’s see how we can reduce the time complexity to O(logN). We can use the idea of binary search here.

For arrays arr1 and arR2 of length N, the upper median is the NTH element of the two ordered arrays. So, we can translate this problem to finding the KTH smallest element of two ordered arrays, where k=N.

To find the NTH element, we can compare arr1[N/2-1] with arr2[N/2-1], where the “/” stands for integer division. Due to arr1 [N / 2-1] and arr2] [N / 2-1 in the front of the respectively arr1 [0.. N / 2-2] and arr2 [0.. N / 2-2), N / 2 to 1. For smaller values of arr1[N/2-1] and ARR2 [N/2-1], there are at most N/2-1+N/2-1= n-2 elements smaller than it, so it is not the NTH smallest element.

Therefore, we can summarize the following three cases.

If ARR1 [N/2-1] < ARR2 [N/2-1], then the numbers smaller than ARR1 [N/2-1] are at most only the first N/2-1 of ARR1 and the first N/2-1 of ARR2, that is, the numbers smaller than ARr1 [N/2-1] are at most n-2. Therefore, arr1[N/2-1] cannot be the NTH digit, nor can arr1[0] through arr1[N/2-1] be the NTH digit, so it can be deleted.
If ARR1 [N/2-1] > ARR2 [N/2-1], then arR2 [0] to ARR2 [N/2-1] can be excluded.
If ARR1 [N/2-1]== ARR2 [N/2-1], it can be classified as the first case for processing.

As you can see, after one round of comparison, we can look at N over 2 numbers that can’t possibly be the NTH smallest, and we’ve cut our search in half. At the same time, we’re going to continue the binary search on the new array that we excluded, and we’re going to decrease the value of N depending on how many we excluded, because none of the excluded numbers are larger than the NTH smallest number.

Let’s look at a concrete example.

Class Solution: def findMedianSortedArrays(self, arr1, arr2): N= len(arr1) Return min(arr1[0],arr2[0]) index1, index2 = 0, 0 new_index1 = index1 + k // 2 - 1 new_index2 = index2 + k // 2 - 1 data1, data2 = arr1[new_index1], Arr2 [new_index2] # if data1 <= data2: k=k-k//2 # if new_index1+1 else: Index2 = new_index2 + 1 return min(arr1[index1],arr2[index2])Copy the code

snacks

If two ordered arrays are given different sizes, that is, two positive ordered (from small to large) arrays nums1 and nums2 of size m and n are given. Please find and return the median of the two positive ordinal groups.

According to the definition of the median, when m+n is odd, the median is the (m+n+1)/2 element of two ordered arrays. When m+n is even, the median is the average of the (m+n)/2 and (m+n)/2+1 elements of two ordered arrays. So we can convert this problem to the KTH smallest number for finding two ordered arrays, where k is (m+n)/2 or (m+n)/2+1.

So this is going to be similar to what we did in the last problem, but there are a couple of special cases here.

If nums1[k/2-1] or nums[k/2-1] is out of bounds, then we need to select the last element of the corresponding array, namely min(k/2-1,m-1) or min(k/2-1,n-1).
If one array is empty, we can simply return the KTH smallest element in the other array.
If k=1, we just need to return the minimum value of the first element of both arrays.

Let’s look at the implementation of the code.

Def findMedianSortedArrays(self, nums1, nums2): def getKthElement(self, nums1, nums2): Index1, index2 = 0, 0 while True: if index1 == m, then return the KTH element of the other array: Return nums2[index2 + k-1] if index2 == n: return nums1[index1 + k-1] if k == 1 Return min(nums1[index1], nums2[index2]) New_index1 = min(index1 + k // 2-1, m-1) # New_index2 = min(index2 + k // 2-1, n-1) data1, data2 = nums1[new_index1], Nums2 [new_index2] # if data1< = data2 if data1< = data2: New_index1 + 1 k -= new_index1 - index1 + 1 else N = len(nums1) n = len(nums1) n = len(nums1) n = len(nums1) Len (nums2) # the median is the average of lens/2 and lens/2+1 if the median is even if lens/2 == 1: Else: return (getKthElement(lens // 2) + getKthElement(lens // 2 + 1)) / 2.0Copy the code

The time complexity of this algorithm is O(log(m+n)) and the space complexity is O(1).

The first positive integer missing

Problem description

LeetCode 41. Missing the first positive number

Given an unsorted nums array of integers with no duplicate elements, find the smallest positive integer that does not appear.

You implement a solution with O(n) time complexity and use only constant level extra space.

Example:

Input: nums = [1,2,0]

Output: 3

To analyze problems

For an array of length N with no repeating elements, the smallest integer that does not occur in the array can only occur in [1,N+1]. This is because if [1,N] occurs in both, the array is filled. The answer is N+1, otherwise it is the smallest integer that does not occur in [1,N]. Temp [i-1] = I, temp[i-1] = I, temp[i-1] = I, temp[i-1] = I, temp[i-1] = I, temp[i-1] = I After the traversal is complete, the smallest positive integer that does not meet the temp[i-1] = I condition is the smallest positive integer. If both conditions are met, the smallest positive integer is N+1.

Let’s take a look at the code implementation.

Class Solution: def firstMissingPositive(self, nums): n = len(nums) temp = [0]*n for I in range(n): If nums[I] <= 0 or nums[I] > N: continue else: Temp [I]-1]=nums[I] temp[I]-1 =nums[I] For I in range(n): if temp[I]! = I +1: return I +1 # return N+1 if both existCopy the code

We can know that the time complexity and space complexity of the algorithm are O(n), obviously the space complexity does not meet the requirements of the problem, so how can we reduce the space complexity of the algorithm? The secondary array is the same size as the original array, so can we reuse the original array NUMs? The answer is clearly yes. If x belongs to [1,N], we will swap the elements of element X and nums[x-1] so that X appears in the correct position. Otherwise, no processing will be done. When traversal is complete, the first positive integer in NUMS that does not satisfy nums[i-1] = I is the smallest positive integer. If both are satisfied, then the smallest positive integer is N+1.

Let’s look at the implementation of the code.

Class Solution: def firstMissingPositive(self, nums): self = len(nums) While nums[I] <= nums[I] <= n \ and nums[I] -1 = nums[I] -1 = nums[I] -1 = nums[I]: = nums[I] -1, nums[I] = nums[I] -1, nums[I] = nums[I] -1, nums[I] -1 For I in range(n): if nums[I]! = I +1: return I +1 # return n+1Copy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).

Rotate the array clockwise

Problem description

01.07. Rotation matrix

There is an NxN integer matrix, write an algorithm to rotate the matrix 90 degrees clockwise.

Requirements: Time complexity O(N^2), space complexity O(N^2).

Advanced: time complexity is O(N^2), space complexity is O(1)

Example:

[[[5, 1, 9, 11], rotate 90 degrees after [15, 13, 2, 5], [2, 4, 8, 10], = = = = = = = = = = = = > [14, 3, 4, 1], [13, 3, 6, 7], [12, 6, 8, 9]. [15,14,12,16] [16, 7,10,11]]Copy the code

To analyze problems

For the first row of elements in the matrix, after a 90-degree rotation, they appear in the position of the penultimate column, as shown in the figure below.

And the ith element in the first row happens to be the ith element in the penultimate column after the rotation. The same is true for the element in the second row, which becomes the element in the penultimate column after rotation, and the ith element in the second row happens to be the ith element in the penultimate column after rotation. Therefore, we can get the rule that for the JTH element in the ith row of the matrix, after rotation, it appears in the JTH position in the ith column to the last, that is, for the matrix[I] [j] element in the matrix, after rotation, its new position is matrix[j] [n-i-1].

So, we apply a new matrix of size n by n to temporarily store the rotated results. We iterate over all the elements in the matrix and store the elements in the corresponding positions in the new matrix according to the above rules. After traversal, copy the new matrix to the original matrix. Let’s take a look at the code implementation.

class Solution(object): def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, Temp = [[0] * n for _ in range(n)] temp = [[0] * n for _ in range(n)] For I in range(n): for j in range(n): temp[j][n-i-1] = matrix[I][j] # copy auxiliary matrix to matrix[:] = tempCopy the code

The time complexity of the algorithm is O(N^2), the space complexity is O(N^2).

The advanced

So how do we rotate the matrix in place without using the auxiliary space? For the elements in matrix, we use the formula **temp[j] [n-i-1] = matrix[I] [j]** for rotation. If we do not apply for auxiliary matrix, we directly apply the element matrix[I] [j], If the matrix[j] [n-i-1] is placed in the position of matrix **matrix[j] [n-i-1], the matrix[j] [n-i-1]** elements in the original matrix are covered, which is obviously not the result we want.

Now that we know how to rotate the matrix in place, there is one more thing to be clear about: which locations should we pick for the above in-place swap operation? According to the above analysis, four positions can be exchanged at one time, so:

When n is even, we need to select n^ 2/4 = (n/2) * (n/2) elements for in-situ exchange operation, which can be divided into four blocks to ensure no repetition and rotation of all elements;
When n is odd, since the position of the center remains unchanged after rotation, we need to select (n^2-1)/4=(n-1)/2 * (n+1) /2 elements for in-place exchange operation. Taking the 5*5 matrix as an example, it can be divided in the following way to ensure that all elements are rotated without repetition or omission.

Let’s look at the implementation of the code.

Class Solution(object): def rotate(self, matrix): def rotate(self, matrix): def rotate(self, matrix): for j in range((n + 1) // 2): # Take one turn in place, Temp = matrix[I][J] matrix[I][J] = matrix[n-j-1][I] matrix[n-j-1][I] = matrix[n-i-1][N-J-1] matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1] matrix[j][n - i - 1] = tempCopy the code

The time complexity of this algorithm is O(n^2) and the space complexity is O(1).

The longest continuous subsequence in an array

Problem description

LeetCode128. Longest continuous sequence

Given an unordered array arr, return the length of the longest continuous subsequence in the array. Please design and implement the time complexity of O(n) algorithm to solve this problem.

Example:

Input:,4,200,1,3,2 [100]

Output: 4

Description: The longest sequence of consecutive digits is [1, 2, 3, 4]. It has length 4.

To analyze problems

Given that the array is unordered, the most intuitive idea is to iterate through each element of the array and consider using it as a starting point to continuously search the array for x+1, x+2… If the longest match is x+n, then it means that the longest continuous sequence starting from x is x, x+1, x+2… X plus n, which has length n plus 1. Because it takes O(n) time to find a number in an array; The time complexity of O(1) is only needed to determine the existence of a number in the hash table, so we can reduce the time complexity of the algorithm by introducing a hash table.

In the worst case, the time complexity of the algorithm is O(n^2) (that is, the outer layer needs to enumerate n numbers, and the inner layer also needs to match n times), which cannot meet the requirements of the problem, so how can we optimize it?

If we know that the array has an x, x+1, x+2… , a continuous sequence of x+n, then we do not need to continue with x+1, x+2,…. I’m going to look for continuous sequences in the array starting from x plus n, because I’m not going to get any better than a continuous sequence starting from x. So, if we’re in the outer loop we can just skip it.

Specifically, when we traverse the element X, we try to determine whether its precursor x-1 exists. If so, we do not need to perform the following logic, because the result of matching from x-1 is better than that of matching from x, so we skip x.

Let’s look at the implementation of the code.

class Solution: def longestConsecutive(self, nums): Num_set = set(nums) for num in num_set: If num-1 is not in num_set, skip if num-1 is not in num_set. While currentData + 1 in num_set Currentdata += 1 currentLength += 1 # Take the maximum length = Max (currentLength, length) return lengthCopy the code

The time complexity of this algorithm is O(n), and the space complexity is also O(n).

Looking for peak

Problem description

LeetCode 162. Look for peaks

Peak elements are those whose values are strictly greater than their left and right neighbors. Given an integer array nums, find the peak element and return its index. The array may contain multiple peaks, in which case you simply return the location of any one of the peaks. You can assume that NUMs [-1] = nums[n] = -∞. You have to implement order log n time to solve this problem.

Example:

Input: nums = [1,2,3,1]

Output: 3 is the peak element, and your function should return its index 2.

To analyze problems

A peak is an element whose value is strictly greater than its left and right neighbors, so obviously the maximum value in an array must be a peak, because it must be greater than the elements to its left and right. So, we can walk through the array once and figure out where the maximum value is. The time complexity of this algorithm is O(n), which does not meet the requirements of the problem. So how do we optimize.

The way to think about it is, if we start at one place and keep going up, we will eventually reach a peak.

Therefore, we first randomly select an initial position I within the range [0, n], and then decide which direction to go according to the relationship between NUMs [i-1], NUMs [I], and NUMs [I +1].

If nums[i-1] < nums[I] > nums[I +1], then position I is the peak position, we return I directly.
If nums[i-1] < nums[I] < nums[I +1], then position I is in an uphill position. To find the peak value, you need to go right, i.e. I = I +1.
If nums[i-1] > nums[I] > nums[I +1], then position I is in the downhill position, to find the peak, you need to go left, season I =i-1.
If nums[i-1] > nums[I] < nums[I +1], then I is at the bottom of the slope, and to find the peak, we can go in either direction, assuming that we need to go to the right in this case.

So to sum up, when I is not the peak.

If nums[I] > nums[I +1], I needs to go to the left, that is, I =i-1.
If nums[I] is less than nums[I +1], I needs to go to the right, that is, I = I +1.

import random class Solution: def findPeakElement(self, nums): Idx = random. Randint (0, n-1) def get_value(I) def get_value(I): if i == -1 or i == n: Float ('-inf') return nums[I] # float('-inf') return nums[I] # float('-inf') return nums[I] # While not (get_value(IDx-1) < get_value(IDx) > get_value(IDx + 1)): if (idx) < get_value(idx + 1): idx = idx + 1 else: idx = idx - 1 return idxCopy the code

In the worst case, if nums is monotonically increasing, and we start at 0, then we have to go all the way to the right to the last position in the array, which is O(n), which is O(logn), which is not true, how do we solve it? For time complexity of the form O(logn), the first thing that comes to mind is dichotomy, but the elements in the array are not sorted, so how can we use dichotomy to solve this problem? Let’s take a look.

Through analysis, we can see that when nums[I] < nums[I +1], we need to move I to the right, i.e. I = I +1, so that all positions to the left of I and I will never be reached in subsequent iterations. If you want to go left to position I, nums[I] > nums[I +1], which is obviously impossible. Therefore, we can design the following algorithm. First, create two variables L and r to represent the left and right boundaries that can be walked. At the beginning, L =0 and r=n-1.

Take the midpoint of the interval [L, r], i.e. mid=(L +r)/2.
If the subscript mid is the peak value, return it.
If nums[mid] < nums[mid+1], the peak value is to the right of mid, so discard the range [l, mid] and look for the rest of the range [mid+1, r].
If nums[mid] > nums[mid+1], the peak value is to the left of mid, so discard [mid, r] and search for the rest of [l, mid-1].

In this case, the algorithm eliminates half the elements at a time, so the time is order logn.

Let’s look at the implementation of the code.

Class Solution: def getPeakElement (self, nums): n = len(nums) If I == -1 or I == n: return float('-inf') return nums[I] #l,r =0 r=n-1 ans=-1 while l <= r: If mid = (mid) < mid > get_value(mid) < mid > get_value(mid + 1); If get_value(mid) < get_value(mid +1); if get_value(mid) < get_value(mid +1); if get_value(mid) < get_value(mid +1); l = mid + 1 else: r = mid - 1 return ansCopy the code

Lookup in a two-dimensional array

Problem description

LeetCode refers to the search in Offer 04. Two-dimensional array

In an N by m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Perform an efficient function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

Example:

The existing matrix matrix is as follows:

[[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]]Copy the code

Given target = 9, return true.

Given target = 20, return false.

To analyze problems

To find an element in a two-dimensional array, we can iterate over every element in the two-dimensional array and determine if it matches the target value. The time complexity of this algorithm is O(m*n), which is obviously not the optimal solution. Let’s take a look at how to optimize.

Because every row, every column in a given array is incrementally sorted. When we start at the bottom left corner, there are only two choices: up and right, the top value is strictly small, and the right value is strictly large. So, we can use this property.

We start with the lower left corner of the two-dimensional array and iterate through the array.

When matrix [I] [j] < target, target is to the right of matrix [I] [j], so go right, i.e. execute j=j+1.
Matrix [I] [j] > target, target is above matrix [I] [j], so I = i-1
If matrix [I] [j] == target, return true.

Finally, when the boundary of a two-dimensional array is exceeded, the element does not exist in the array and returns false.

Let’s look at the implementation of the code.

class Solution(object): def findNumberIn2DArray(self, matrix, target): """ :type matrix: List[List[int]] :type target: Int :rtype: bool """ m=len(matrix) # Return False n=len(matrix[0]) # return False n=len(matrix[0]) # Matrix [I][j] == target: return True # > elif matrix[I][j] > target: Elif matrix[I][j] < target: j = j + 1 return FalseCopy the code

The time complexity of the algorithm is O(m+n) and the space complexity is O(1).

Pairs of inversions in an array

Problem description

LeetCode refers to the reverse pair in the Offer 51 array

Two digits in an array form a reverse pair if the preceding digit is larger than the following digit. Enter an array and find the total number of inversions P in the array.

Example:

Input:,5,6,4 [7]

Output: 5

To analyze problems

The most likely violent solution to this problem is to use a two-layer for loop to judge whether it constitutes an inverse relationship one by one.

Class Solution: def reversePairs(self, nums) : n = len(nums) For I in range(0, n-1): for j in range(I + 1, n): if nums[I] > nums[j]: if nums[I] > nums[j]: res += 1 return resCopy the code

The time complexity of this algorithm is O(n^2) and the space complexity is O(1).

This algorithm is obviously not optimal, and we first heard of the concept of reverse pairs, I think, when we sort arrays. So, we can use merge sort algorithm here to solve the number of inversions.

So first of all, let’s review what merge sort is. Merge sort is a typical application of divide-and-conquer. It consists of the following three steps:

Decomposition: Assuming that the interval to be sorted is [L,r], we set mid=(L +r)//2, and divide the interval into [L,mid] and [mid+1,r].
Solution: Use merge sort recursively to solve two subsequences, so that the order.
Merge: Combine two sorted subsequences [L,mid] and [mid+1,r].

Now let’s see how we can use merge sort to solve for inversions, okay? The key lies in the merging step of merge sort, that is, by using the partial order of array, the number of inversions before or after a number can be calculated at a stroke. Let’s look at a specific example. Assume that there are currently two sorted sequences waiting to be merged, L=[8,17,30,45] and R=[10,24,27,39], as shown in the figure below.

Let’s see how we can combine L and R into an ordered array. The idea is to copy the original array into the auxiliary array, and then use the two-pointer method to merge the smaller elements back each time.

Let’s look at the implementation of the code.

Class Solution: def reversePairs(self, nums) : n = len(nums) Temp = [0 for _ in range(n)] return self. Reverse_pairs (nums, 0, n-1, Nums def reverse_pairs(self, nums, left, right, temp): if left == right: Return 0 mid = (left + right)//2 Reverse_pairs (nums, left, mid, temp) Right_pairs = self. Reverse_pairs (nums, mid + 1, right, Temp) # subsequence [left, mid] and [mid + 1, Reverse_pairs = left_pairs + pairs #nums[mid] <= nums[mid + 1] Reverse_pairs if nums[mid] <= nums[mid + 1]: Return reverse_pairs # Reverse pairs = self. Merge_and_count (nums, left, mid, right, temp) return reverse_pairs + cross_pairs def merge_and_count(self, nums, left, mid, right, temp): [mid + 1, right + 1] : [mid + 1, right + 1] : [mid + 1, right + 1] : [mid + 1, right + 1] : [mid + 1, right + 1] : temp[i] = nums[i] i = left j = mid + 1 res = 0 for k in range(left, right + 1): Insert right into nums if I >mid: Nums [k] = temp[j] j += 1 #j>right Elif temp[I] <= temp[j]: nums[k] = temp[I] I += 1 # Nums [k] = temp[I] I += 1 nums[k] = temp[I] I += 1 nums[k] = temp[j] j += 1 res += (mid - i + 1) return resCopy the code

The time complexity of this algorithm is O(nlogn) and the space complexity is O(1).

Rotate the array

Problem description

LeetCode189. Rotate array

If there are n integers in array A, move each integer to the right by M (M >=0) without allowing the use of other arrays. An-1 becomes (An-m… The An – 1 A0 A1… An-m-1) (the last m number circulates to the first m positions).

Example:

Input:,2,3,4,5,6,7 [1]

Output:,6,7,1,2,3,4 [5]

To analyze problems

The intuitive idea of this problem is to use extra arrays to put each element in the right place. We use n to represent the length of the array, then iterate over the array, place the element with subscript I in the new array at subscript (I +k) % n, and finally copy the new array into the original array.

class Solution: def rotate(self,nums,k): n=len(nums) tmp=[0]*n for i in range(0,n): TMP [(I +k)%n]=nums[I]Copy the code

The time complexity of this algorithm is O(n), and the space complexity is also O(n). But it is not allowed to use another array, obviously this algorithm does not meet the question. When we move the array k times to the right, k mod n elements move to the head of the array, and the rest of the elements move back k mod n. So we can use the method of array flipping to solve. The idea is as follows: first we flip all the elements so that k mod n elements are moved to the head of the array. Then we flip the elements of the interval [0, (k mod n)-1] and the elements of the interval [k mod n, n-1] to get the final answer.

Let’s look at the implementation of the code.

Def reverse(self,nums,start,end): while start < end: tmp=nums[start] nums[start]=nums[end] nums[end]=tmp start=start+1 end=end-1 def rotate(self,nums,k): Self. Reverse (nums,0,k-1) # reverse(nums,0,k-1) # reverse(nums,0,k-1) # reverse(nums,0,k-1) # self.reverse(nums,k,n-1)Copy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).

Reorder the array so that the odd number precedes the even number

Problem description

Take an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the last half of the array.

Example:

Input: [1, 2, 3, 4]

Output:,3,2,4 [1]

To analyze problems

This problem we can use the double pointer method to solve, the specific idea is as follows.

First, we apply two Pointers I and j to the left and right ends of nums, that is, I =0 and j=n-1.
When I points to an odd position, execute I = I +1 until an even number is encountered.
When j points to an even position, perform j=j-1 until an odd number is encountered.
The values of nums[I] and nums[j] are then swapped
Repeat until I ==j.

Let’s look at the implementation of the code.

Class Solution(object): def exchange(self, nums): def exchange(self, nums) =len(nums)-1 While I < j and nums[I] % 2 == 1: While I < j and nums[j] % 2 == 0: j = j - 1 nums[i], nums[j] = nums[j], nums[i] return numsCopy the code

In fact, we can also use the fast and slow pointer method to solve this problem. First, we define two Pointers fast and slow. The function of fast is to search forward where the odd number is, while the function of slow is to point to where the next odd number should be stored. As FAST moves forward, when it searches for an odd number, it swaps it with NUMs [slow], and then moves Slow forward one position, repeating the process until FAST points to the end of the array.

Class Solution: def exchange(self, nums): slow = 0 fast = 0 # change nums[fast] if nums[fast] % 2 == 1 nums[slow], nums[fast] = nums[fast], nums[slow] slow=slow+1 fast=fast+1 return numsCopy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).

Matrix multiplication

Problem description

Given two n by n matrices A and B, find A by B.

Example:

Input: [[1,2], [3,2]], [[3,4], [2,1]]

Output: [[7,6], [13,14]]

To analyze problems

We can use the matrix multiplication rule. For n * n matrix A multiplied by matrix B, the elements of the ith row and j column of matrix C can be expressed as Ci,j=Ai,1* B1,j + Ai,2 * B2,j +… Plus Ai,n times Bn,j, is equal to the product of the ith row of A and the JTH column of B.

class Solution: def solve(self , a, b): N =len(a) res=[[0] *n for _ in range(n)] for I in range(0,n): for j in range(0,n): For k in range(0,n): for k in range(0,n): for k in range(0,n): for k in range(0,n): for k in range(0,n): for k in range(0,n): for k in range(0,n): for k in range(0,n)Copy the code

The time complexity of this algorithm is O(N^3) and the space complexity is O(N^2).

We all know that two-dimensional arrays are actually stored sequentially in computer memory, as follows:

When an operating system loads data into the cache, it loads a batch of data in the vicinity of the hit data into the cache, because the operating system assumes that if a memory location is referenced, the program is likely to reference a nearby memory location in the near future. So we optimize by adjusting the order in which the arrays are read, so that the matrices A and B are read sequentially and then fed into the CPU for computation, making the running time faster. Here’s how to do it:

class Solution: def solve(self , a, b): N =len(a) res=[[0] *n for _ in range(n)] for I in range(0,n): for j in range(0,n): Temp = A [I][j] for k in range(0,n): res[I][k] += temp * b[j][k] return resCopy the code

The time complexity of this algorithm is O(N^3), but it takes advantage of cache optimization to read the elements in array A and array B sequentially, so it generally runs faster than the first method. The spatial complexity of this algorithm is O(N^2).

The number of occurrences of a number in an ascending array

Problem description

Given a non-descending array of length n and a non-negative integer k, count the number of occurrences of k in the array.

Example:

Input:,2,3,3,3,3,4,5 [1], 3

Output: 4

To analyze problems

Regardless of whether the array is ordered or not, if we want to find out if there is an element in the array, all we have to do is walk through the regular array.

class Solution:
    def GetNumberOfK(self,data, k):
        n=0
        for x in data:
            if x==k:
               n=n+1
        return n
Copy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).

Since the array given by the problem is ordered, we can use binary search to solve it. For an ordered array, if we are looking for multiple target values, they must be joined together, so we can use a quadratic binary search to find the upper and lower bounds of the range of target values. First, let’s look at the definitions of upper and lower bounds.

The lower bound is defined as: if there is a target value, it points to the first target value; If not, it points to the first value greater than the target value.
An upper bound is defined as pointing to the first value greater than the target value, regardless of whether the target value exists or not.

Let’s take a look at the code implementation.

Class Solution: def getNumber (self,data, k): count (self,data, k): count (self,data, k): count (self,data, k): count (self,data, k): count (self,data, k): count (self,data, k) Mid = (r+l) // 2 if data[mid] < k: l = mid + 1 else: r = mid left=l mid=(r+l)//2 if data[mid] <= k: l=mid+1 else: r=mid right=l return right - leftCopy the code

The time complexity of this algorithm is O(logN) and the space complexity is O(1).

The largest product of three numbers

Problem description

LeetCode628. Maximum product of three numbers

Given an unordered array A of length N containing positive, negative, and 0, find three numbers that maximize the product and return the product.

Example:

Input: nums = [1,2,3,4]

Output: 24

To analyze problems

The largest product of three numbers in an array has the following two conditions.

If all of the elements in the array are non-negative or non-positive, then the multiplication of the largest three numbers in the array is the largest product.
If the elements in the array have both positive and negative numbers, then the largest product can be either the product of the three largest positive numbers or the product of the two smallest negative numbers (with the largest absolute values) and the largest positive number.

So, all we need to do is find the three largest numbers and the two smallest numbers in the array, and we’ll get the answer. So let’s see how we can solve this. The easiest way to think about it is to sort the array in descending order, so that the first three and last two digits of the sorted array are the largest three and the smallest two.

class Solution:
    def maximumProduct(self,nums):
        nums=sorted(nums)
        n=len(nums)
        return max(nums[0] * nums[1] * nums[n-1], nums[n - 3] * nums[n - 2] * nums[n-1])
Copy the code

The time complexity of the algorithm is O(nlogn), where n is the length of the array. Sorting takes order nlogn time.

The space complexity is O(logn), mainly the overhead of sorting.

We could have scanned the array and found the five numbers, as shown below.

import sys class Solution: def maximumProduct(self,nums): Max1 =max2=max3=-sys.maxsize-1 for x in nums: if x < min1: min2=min1 min1=x elif x<min2: min2=x if x>max1: max3=max2 max2=max1 max1=x elif x>max2: max3=max2 max2=x elif x>max3: max3=x return max(max1*max2*max3,max1*min1*min2)Copy the code

The time complexity of the algorithm is O(n) and the space complexity is O(1).

The last

Originality is not easy! If you think the article is good, you may as well like (reading), leave a message, forward three consecutive go!

The more you know, the more you open your mind. I’ll see you next time.

An array of frequent interview algorithms

The full text overview

The basics of arrays

The definition and characteristics of arrays

There are clever ways to solve the problem

dichotomy

Double pointer method

The sliding window

Hash table method

The sum of two Numbers

Problem description

To analyze problems

To optimize the

Longest non-repeating subarray

Problem description

The sample

To analyze problems

Merges two ordered arrays

Problem description

To optimize the

Spiral matrix

Problem description

To analyze problems

To optimize the

Three numbers neutralized by 0 in the array

Problem description

To analyze problems

The number that occurs more than half The Times in an array

Problem description

To analyze problems

Hash table method

Sorting algorithm

Boyer-moore voting algorithm

Merge range

Problem description

To analyze problems

algorithm

Finds the upper median in two sorted arrays of equal length

Problem description

To analyze problems

The advanced

snacks

The first positive integer missing

Problem description

To analyze problems

Rotate the array clockwise

Problem description

To analyze problems

The advanced

Problem description

To analyze problems

Looking for peak

Problem description

To analyze problems

Lookup in a two-dimensional array

Problem description

To analyze problems

Pairs of inversions in an array

Problem description

To analyze problems

Rotate the array

Problem description

To analyze problems

Reorder the array so that the odd number precedes the even number

Problem description

To analyze problems

Matrix multiplication

Problem description

To analyze problems

The number of occurrences of a number in an ascending array

Problem description

To analyze problems

The largest product of three numbers

Problem description

LeetCode628. Maximum product of three numbers

To analyze problems

The last

Related Posts

A more elegant Zhihu API is based on Python3

You don’t even know the difference between a nil slice and an empty slice? The BAT interviewer will have to send you home to wait for the announcement.