当前位置:网站首页>Byte interview programming question: the minimum number of K
Byte interview programming question: the minimum number of K
2022-04-23 15:09:00 【White horse is not a horse·】
1. Fast algorithm
Front of output k The lowest decimal , All ordered , The time complexity is O(nlogn), Space for O(logn)
package demo1;
import java.util.Arrays;
public class demo2 {
public static void main(String[] args) {
// Fast algorithm
int[] data=new int[]{
1,4,5,3,2,6,7,9,8};
int k=5;
System.out.println(Arrays.toString(data));
fastsort(data,0,data.length-1,k);
System.out.println(Arrays.toString(data));
}
public static void fastsort(int[] data,int first,int last,int k){
// A special case
if(first>last) return ;
// General situation
//1) Find a random number , Exchange on this basis
int left=first;
int right=last;
int temp=data[first]; // The selected benchmark
while(left<right){
//1) Find the object to exchange ( If the left side is the datum , So start on the right and look for )
while(left<right && data[right]>temp) right--;
while(left<right && data[left]<=temp) left++;
//2) Exchange when you find it
if(left<right){
int temp1=data[left];
data[left]=data[right];
data[right]=temp1;
}
}
// Change the position of the benchmark
data[first]=data[left];
data[left]=temp;
// Continue recursion ( With left For boundaries )
if(left+1<k){
fastsort(data,left+2,last, k-left-1);
}else if(left==k){
return;
}else{
fastsort(data,first,left,k);
}
}
}
2. Heap sort
1) Small top heap sorting algorithm ( Through an array , Big pile top , A complete binary tree with child nodes greater than or equal to child nodes )
2) Call to realize the collection of large top heap PriorityQueue, The default is small top heap , Rewritable Comparator Class in compare, Realize the big top reactor .
3) The time complexity is O(nlogn), Spatial complexity O(1)
package demo1;
import java.util.*;
public class demo4 {
public static void main(String[] args) {
List<Integer> list=new ArrayList<>(Arrays.asList(2,3,1,5,7,6,9,8,0));
int k=8;
PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer a,Integer b){
return a-b;
}
});
for(Integer i:list) queue.add(i);
System.out.println(queue);
for(int i=0;i<k;i++) System.out.print(queue.poll()+" ");
}
}
3. Improved fast scheduling algorithm
- Fast scheduling algorithm ( Front of output k The lowest decimal , disorder ), The time complexity is O(n), Space is a constant space
- Learning from the idea of fast platoon , There are multiple choices in recursive operations
package demo1;
import java.util.Arrays;
public class demo3 {
public static void main(String[] args) {
// rewrite : Fast algorithm
int[] data=new int[]{
2,6,7,9,8,1,4,5,3};
//int[] data=new int[]{3,2,4,1,5,8,7};
int k=4;
fastsort(data,0,data.length-1,k);
System.out.println("data="+ Arrays.toString(data));
int[] data1=Arrays.copyOfRange(data,0,k);
System.out.println("result="+ Arrays.toString(data1));
}
public static void fastsort(int[]data,int begin,int end,int k){
// A special case
if(begin>end) return;
// General situation
int left=begin;
int right=end;
int temp=begin;
while(left<right){
// Find something to exchange ( The reference value is... On the left , Look, start on the right )
while(left<right && data[right]>data[temp]) right--;
while(left<right && data[left]<=data[temp]) left++;
// Find it and exchange it
if(left<right){
int tem1=data[right];
data[right]=data[left];
data[left]=tem1;
}
}
// Then the reference value is placed in the position where it should be placed
int tem2=data[left];
data[left]=data[begin];
data[begin]=tem2;
System.out.println("data="+ Arrays.toString(data));
// Perform the following recursive operations ( Core code , Finding the middle position is the reference value
if(left+1<k){
fastsort(data,left+1,end,k);
}else if(left==k || left+1==k ){
return;
}else{
fastsort(data,begin,left,k);
}
}
}
It's easy to get wrong :
1) In the method , First of all, it should be right begin>end Discuss the situation
2) When the appropriate exchange value is found , If the reference value is the first , Then start from the right , Then look to the left
3) Notice the case of recursive selection .
版权声明
本文为[White horse is not a horse·]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231407525012.html
边栏推荐
猜你喜欢
8.4 realization of recurrent neural network from zero
LeetCode165-比较版本号-双指针-字符串
Swift protocol Association object resource name management multithreading GCD delay once
win10 任务栏通知区图标不见了
nuxt项目:全局获取process.env信息
Introduction to Arduino for esp8266 serial port function
API gateway / API gateway (III) - use of Kong - current limiting rate limiting (redis)
Do (local scope), initializer, memory conflict, swift pointer, inout, unsafepointer, unsafebitcast, success
Openfaas practice 4: template operation
Role of asemi rectifier module mdq100-16 in intelligent switching power supply
随机推荐
Llvm - generate addition
Leetcode165 compare version number double pointer string
win10 任务栏通知区图标不见了
LeetCode 练习——396. 旋转函数
Swift - literal, literal protocol, conversion between basic data types and dictionary / array
How does eolink help telecommuting
SSH connects to the remote host through the springboard machine
My raspberry PI zero 2W toss notes to record some problems and solutions
Do (local scope), initializer, memory conflict, swift pointer, inout, unsafepointer, unsafebitcast, success
Leetcode162 - find peak - dichotomy - array
PSYNC synchronization of redis source code analysis
Share 3 tools, edit 5 works at home and earn more than 400
tcp_ Diag kernel related implementation 1 call hierarchy
API gateway / API gateway (II) - use of Kong - load balancing
Redis主从同步
Detailed explanation of C language knowledge points -- first understanding of C language [1] - vs2022 debugging skills and code practice [1]
分享3个使用工具,在家剪辑5个作品挣了400多
setcontext getcontext makecontext swapcontext
My raspberry PI zero 2W tossing notes record some problems encountered and solutions
API gateway / API gateway (III) - use of Kong - current limiting rate limiting (redis)