Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities
1. Title Description
Given an array of length n that may have duplicate values, find the smallest k number in it that does not have to be duplicated. For example, if the array elements are 4,5,1,6,2,7,3,8, the smallest four digits are 1,2,3,4(in any order).
Data range: 0≤ K,n≤10000, the size of each number in the array 0≤ Val ≤1000
Requirements: Space complexity O(n), time complexity O(nlogn)
Example 1
Input:
,5,1,6,2,7,3,8 [4], 4Copy the codeThe return value:
[1, 2, 3, 4]Copy the codeDescription:
Return the smallest four numbers, or [1,3,2,4]Copy the codeExample 2
Input:
[1], 0Copy the codeThe return value:
[]
Copy the codeExample 3
Input:
,1,2,1,2 0 and 3, 3Copy the codeThe return value:
,1,1 [0]Copy the code2. Problem solving and analysis
This is a common interview question, but it can also be used in real situations, such as ranking the top of the list.
(1) sorting method
First of all, the simplest way to achieve this is to sort the entire array, and then output the first K bits. Using fast-sorting and other sorting algorithms, time complexity and space complexity can meet the requirements of the problem, and the number of K returned is still an ordered sequence.
Because there is a better way to do this, the code is implemented directly using go’s sort library.
AC
func GetLeastNumbers_Solution( input []int , k int ) []int {
// write code here
if len(input) <= k{
return input
}
sort.Ints(input)
var res []int
for i := 0; i < k; i++ {
result = append(result, input[i])
}
return res
}
Copy the code
(2) Fast sorting method
Since the sequence they allow us to return is not ordered, we don’t need to do the full sort. For quicksort, as long as we find the KTH number in the middle, after a round of quicksort process, since the number on the left is not greater than the selected node, we return the left and the KTH number; If the selected number is k-1, returning the left number is also eligible.
If the selected number does not match the above, a new round of quicksort needs to be started. If the number of numbers on the left is greater than K, the quicksort process begins on the left. If it is less than K, the value of K needs to be reduced to the remaining number needed, and then the number on the right side of the fast sorting process.
In general, it is on the basis of the original fast row implementation, some adjustments to divide and conquer, can reduce the time complexity.
AC
func GetLeastNumbers_Solution( input []int , k int ) []int {
// write code here
if len(input)
var fastSort func (left, right, k int)
fastSort = func (left, right, k int) {
l, r, tmp := left, right, input[left]
for l < r {
for l < r && tmp <= input[r] {
r--
}
if l < r {
input[l] = input[r]
l++
}
for l < r && tmp >= input[l] {
l++
}
if l < r {
input[r] = input[l]
r--
}
}
input[l] = tmp
if k == l-left+1 || k == l-left {
// The number of left intervals or the number of intermediate nodes reaches the requirement
return
}
if k < l-left {
// There are too many left sections
fastSort(left, l- 1, k)
return
}
if k > l-left+1 {
// The left interval plus the middle is not enough
fastSort(l+1, right, k-(l-left+1))
return
}
return
}
fastSort(0.len(input) - 1, k)
return input[:k]
}
Copy the code
(3) the maximum heap
Using the maximum heap (priority queue) can effectively solve the minimum number problem.
We need to do two steps:
- When the number of elements in the heap is less than K, the heap is directly entered.
- When the number of heap elements is equal to K, the new element is compared to the top element (the largest number in the heap), and if the new element is smaller, the heap is pushed out of the heap, and the element is put into the heap.
The add and delete operations of the maximum heap cost O(logn), plus the traversal cost O(n), so the total time complexity is O(nlogn).
The difficulty is how to implement a heap, and here is some code borrowed from other big guys.
AC
type IntHeap []int
func (h IntHeap) Len(a) int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))}func (h *IntHeap) Pop(a) interface{} {
old := *h
n := len(old)
x := old[n- 1]
*h = old[0 : n- 1]
return x
}
func GetLeastNumbers_Solution( input []int , k int ) []int {
// write code here
if k <= 0 || k > len(input) {
return []int{}
}
hp := &IntHeap{}
*hp = input[:]
heap.Init(hp)
res := make([]int.0)
for i := 0; i < k; i++{
res = append(res,heap.Pop(hp).(int))}return res
}
Copy the codeThird, summary
A large amount of coding time can be left by sorting and taking the first K number. However, when the amount of data increases, the time consumption of this algorithm will be significantly different from other methods, so it is not recommended to use it.
Then there is the optimization of the first sort, where only part of the sort operation is performed so that meaningless calculations can be avoided and performance can be improved. However, because the original array needs to be modified, you need to select it according to the actual situation.
Finally, the maximum heap is used to implement a priority queue. This method should be one of the best solutions. Its advantage is that the calculation can be implemented without loading all the data into memory, and the minimum number of K can be dynamically updated as the input. Go’s basic library in this area is relatively simple and requires us to implement the relevant functions manually.