<> Interview questions 40. least k number

Input integer array arr , Find the smallest k number . for example , input 4,5,1,6,2,7,3,8 this 8 Number , The smallest 4 The number is 1,2,3,4.

Example 1:

input :arr = [3,2,1], k = 2
output :[1,2] perhaps [2,1]
Example 2:

input :arr = [0,1,2,1], k = 1
output :[0]

<> Problem solving 1
public int[] getLeastNumbers(int[] arr, int k) { sort(arr); int[] ints = new
int[k]; for (int i = 0; i < k; i++) { ints[i] = arr[i]; } return ints; } public
static void sort(int []arr){ //1. Construction of large top reactor for(int i=arr.length/2-1;i>=0;i--){
// From the first non leaf node to the top , Adjust structure from right to left adjustHeap(arr,i,arr.length); } //2. Adjust heap structure + Swap heap top and end elements
for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);// Exchange the heap top element with the last element adjustHeap(arr,0
,j);// Readjust the heap } } /** * Adjusting the large top reactor ( Adjustment process only , Based on the construction of the large top reactor ) * @param arr * @param i *
@param length */ public static void adjustHeap(int []arr,int i,int length){ int
temp= arr[i];// Take out the current element first i for(int k=i*2+1;k<length;k=k*2+1){
// from i Start of left child of node , that is 2i+1 Start at if(k+1<length && arr[k]<arr[k+1]){
// If the left sub node is smaller than the right sub node ,k Point to right child node k++; } if(arr[k] >temp){// If the child node is larger than the parent node , Assign child values to parent ( No exchange )
arr[i] = arr[k]; i = k; }else{ break; } } arr[i] = temp;// take temp Value to final position } /** *
Exchange element * @param arr * @param a * @param b */ public static void swap(int []arr,int
a,int b){ int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; }
<> Problem solving 2
import java.util.Arrays; import java.util.HashMap; import java.util.Map; /** *
@Auther: truedei * @Date: 2020 /20-5-20 08:45 * @Description: */ public class
Test { static public int[] getLeastNumbers(int[] arr, int k) { Arrays.sort(arr);
int[] ints = new int[k]; for (int i = 0; i < k; i++) { ints[i] = arr[i]; }
return ints; } public static void main(String[] args) { int [] a =new int[] {3,2
,1}; int[] leastNumbers = getLeastNumbers(a, 2); for (int number : leastNumbers)
{ System.out.println(number); } } }

Technology
©2019-2020 Toolsou All rights reserved,
Mybatis Error resolution :There is no getter for property named '*' in 'class Java.lang.String Big data tells you , How tired are Chinese women Message quality platform series | Full link troubleshooting Gude Haowen serial - You deserve to be an engineer ( Preface ) Image explanation of over fitting and under fitting Springboot of JPA Common query methods JAVA Detailed explanation of anomalies vue Of v-if And v-show The difference between python To solve the problem of dictionary writing list in Codeup——601 | problem A: task scheduling