当前位置:网站首页>Cartoon: looking for the k-th element of an unordered array (Revised)
Cartoon: looking for the k-th element of an unordered array (Revised)
2022-07-05 17:28:00 【Small ash】
This article modifies two details :
1. Method 2 , Insert the array A The condition is to traverse to the element “ Greater than ” Array A The smallest element of , Instead of ” Less than ”.
2. Method 3 , node 24 When the little top pile sinks , It should be connected to nodes 17 In exchange for , Not with nodes 20 In exchange for .
Thank you for your correction .
————— the second day —————
What does the title mean ? For example, given an unordered array as follows :
If k=6, That is to look for the second 6 Big elements , Which element is this ?
obviously , The largest element in the array is 24, The second largest element is 20, The third element is 17 ...... The first 6 The big element is 9.
Method 1 : Sequencing
This is the easiest way to think of , First, sort the unordered array from large to small , After the order k Elements , Nature is the number one in the array k Big element .
Method 2 : Insertion method
Maintain a length of k Array of A Ordered array of , Used to store known k A larger element .
Next, traverse the original array , Every time you traverse to an element , And an array A Compared with the smallest element in , If it is less than or equal to the array A The smallest element of , Continue traversing ; If it's larger than the array A The smallest element of , Then insert it into the array A in , And put the smallest element ever “ Squeeze out ”.
such as k=3, Let's start with the leftmost 7,5,15 Put three numbers in an array in order A among , Represents the current three largest numbers .
Now , Traversing 3, because 3<5, Continue traversing .
Next we go through to 17, because 17>5, Insert into array A The right place , Similar to insert sort , And put the smallest element 5“ Squeeze out ”.
Continue traversing the original array , All the way to the last element of the array ......
Final , Array A The elements stored in are 24,20,17, Represents the largest... In the entire array 3 Elements . Now the array A The smallest element in 17 That's what we're looking for k Big element .
————————————
What is a binary heap ? If you don't know much about it, you can read this article first : comic : What is a binary heap ?( Revised version )
In short , A binary heap is a special kind of complete binary tree , It consists of two forms: large top pile and small top pile .
Among them, the characteristics of small top reactor , Every parent node is less than or equal to its own child node . To solve this algorithmic problem , We can use Small cap pile Characteristics of .
Method 3 : Small top pile method
Maintain a capacity of k The little top pile , Heap k Nodes represent The biggest... At present k Elements , And the top of the pile is obviously this k Of the elements minimum value .
Iterate over the original array , One element per iteration , Compared to the top of the heap , If the current element is less than or equal to the top of the heap , Then continue to traverse ; If the element is larger than the top of the heap , Put the current element at the top of the heap , And adjust the fork stack ( Sinking operation ).
After the traversal is over , The top of the heap is an array Maximum k The minimum of the elements , That is to say The first k Big element .
hypothesis k=5, The specific implementation steps are as follows :
1. Put the front of the array k Elements are built into a heap .
2. Continue traversing the array , Compared to the top of the heap , If it is less than or equal to the top of the heap , Then continue to traverse ; If it's larger than the top of the pile , Replace the top element and adjust the heap .
Traverse to element 2, because 2<3, So continue traversing .
Traverse to element 20, because 20>3,20 Instead of the top position , And adjust the pile .
Traverse to element 24, because 24>5,24 Instead of the top position , And adjust the pile .
And so on , We traverse the elements one by one , When traversing to the last element 8 When , The situation of small top reactor is as follows :
3. The top of the heap at this time , It's the minimum in the heap , That is, the first in the array k Big element .
What is the time complexity of this method ?
1. The time complexity of building a heap is O(k)
2. The time complexity of traversing the remaining array is O(n-k)
3. The time complexity of each heap adjustment is O(logk)
among 2 and 3 It's a nested relationship ,1 and 2,3 It's juxtaposition , So the total worst-case time complexity is O((n-k)logk + k). When k Far less than n Under the circumstances , It can also be approximately regarded as O(nlogk).
What is the spatial complexity of this method ?
Just now, we showed the binary heap separately in the detailed steps , To make it easy to understand . But if it's allowed to change the original array , We can put the front of the array k Elements “ In situ exchange ” To build a binary reactor , This eliminates the need to open up additional storage space .
therefore , The spatial complexity of the method is O(1).
/**
* Search for the first k Big elements
* @param array The heap to be adjusted
* @param k What is the largest
*/
public static int findNumberK(int[] array, int k){
//1. Before use k Elements to build a small top heap
buildHeap(array, k);
//2. Continue traversing the array , Compared to the top of the heap
for(int i=k; i<array.length;i++){
if(array[i] > array[0]){
array[0] = array[i];
downAdjust(array, 0, k);
}
}
//3. Return to the top of heap element
return array[0];
}
/**
* Build heap
* @param array The heap to be adjusted
* @param length The effective size of the heap
*/
private static void buildHeap(int[] array, int length) {
// Start with the last non leaf node , Adjust in turn
for (int i = (length-2)/2; i >= 0; i--) {
downAdjust(array, i, length);
}
}
/**
* Sinking adjustment
* @param array The heap to be adjusted
* @param index The node to sink
* @param length The effective size of the heap
*/
private static void downAdjust(int[] array, int index, int length) {
// temp Save the parent node value , For the final assignment
int temp = array[index];
int childIndex = 2 * index + 1;
while (childIndex < length) {
// If there is a right child , And the right child is less than the left child , Then locate the right child
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
// If the parent node is less than the value of any child , Direct jump out
if (temp <= array[childIndex])
break;
// There's no real exchange , One way assignment is enough
array[index] = array[childIndex];
index = childIndex;
childIndex = 2 * childIndex + 1;
}
array[index] = temp;
}
public static void main(String[] args) {
int[] array = new int[] {7,5,15,3,17,2,20,24,1,9,12,8};
System.out.println(findNumberK(array, 5));
}
Method four : Divide and conquer method
We all know about quick sort , Quicksort uses divide and conquer , Divide the array into larger and smaller parts each time .
We're looking for number one k When it comes to big elements , You can also use this idea , With a certain element A Benchmarking , Make greater than A Are swapped to the left of the array , Less than A All of the elements are swapped to the right of the array .
For example, we choose elements 7 As a benchmark , Divide the array into larger ones on the left , Two smaller areas on the right , The exchange results are as follows :
Including elements 7 The larger elements inside are 8 individual , But our k=5, Obviously there are too many larger elements . So we continue to divide and conquer the larger element regions , This time with elements 12 Bit reference :
thus , Including elements 12 The larger elements inside are 5 individual , Coincides with k equal . therefore , Reference elements 12 That's what we're looking for .
This is the general idea of divide and conquer , The time complexity of this method is even better than that of the small top pile method , You can achieve O(n). Interested partners can try to use the code to achieve it .
Found this article useful , Please give it a good look , I think it's very useful , Please forward it to your friends .
边栏推荐
- WR | 西湖大学鞠峰组揭示微塑料污染对人工湿地菌群与脱氮功能的影响
- Rider 设置选中单词侧边高亮,去除警告建议高亮
- 漫画:寻找无序数组的第k大元素(修订版)
- What else do you not know about new map()
- 7. Scala class
- How MySQL uses JSON_ Extract() takes JSON value
- Zhang Ping'an: accelerate cloud digital innovation and jointly build an industrial smart ecosystem
- Read the basic grammar of C language in one article
- EasyX second lesson
- 世界上最难的5种编程语言
猜你喜欢
基于Redis实现延时队列的优化方案小结
In depth understanding of redis memory obsolescence strategy
兰空图床苹果快捷指令
Use of ThinkPHP template
winedt常用快捷键 修改快捷键latex编译按钮
CMake教程Step1(基本起点)
Oracle缩表空间的完整解决实例
北京内推 | 微软亚洲研究院机器学习组招聘NLP/语音合成等方向全职研究员
How to write a full score project document | acquisition technology
Three traversal methods of binary tree
随机推荐
In depth understanding of redis memory obsolescence strategy
NPM installation
基于51单片机的电子时钟设计
Machine learning 01: Introduction
張平安:加快雲上數字創新,共建產業智慧生態
Which is more cost-effective, haqu K1 or haqu H1? Who is more worth starting with?
Cmake tutorial step6 (add custom commands and generate files)
Force deduction solution summary 1200 minimum absolute difference
【testlink】TestLink1.9.18常见问题解决方法
Zhang Ping'an: accelerate cloud digital innovation and jointly build an industrial smart ecosystem
域名解析,反向域名解析nbtstat
Error in compiling libssh2. OpenSSL cannot be found
Embedded-c Language-3
Embedded -arm (bare board development) -2
CMake教程Step6(添加自定义命令和生成文件)
Embedded UC (UNIX System Advanced Programming) -3
[binary tree] insufficient nodes on the root to leaf path
【jmeter】jmeter脚本高级写法:接口自动化脚本内全部为变量,参数(参数可jenkins配置),函数等实现完整业务流测试
Embedded-c Language-1
Function sub file writing