Find the k in the array arr big odd, if not it returns 0. (arr [I] & gt; 0 (i>=0))
Calculate the time complexity (note that code comments, cannot use the built-in sort function)
Format:
Public int findKth (int [] arr, int k) {

//code
}

CodePudding user response:

This is the most basic algorithm, give you an idea, the code is not wrote
Define a temporary array of length k TMP
Traverse the arr, arr [I] respectively with TMP [0, 1]... k, if is greater than the TMP element, then the arr [I] insert TMP, insert location elements were moving back (position is greater than k is automatically discarded), finally return to TMP [k] can
If the requirements cannot be repeated in the insert more than one step in the process of operation, is if TMP does not exist in the arr [I] is inserted, otherwise not inserted

CodePudding user response:

Write a simple, regardless of the repeated

 public class Sample {
Public static void main (String [] args) {
Try {
Int [] a={1,3,5,4,6,2}; 
Int m=findKth (a, 3); 
System. The out. Println (m); 

} the catch (Exception e) {
E.p rintStackTrace (); 
} 
} 

Public static int findKth (int [] arr, int k) {
If (k & gt; Arr. Length) return 0; 
Int [] TMP=new int [k].//define a long array k 
TMP [0]=arr [0]. 
int j=0; 
For (int I=1; ifor (j=0; jIf (arr [I] & gt; TMP [j]) break;//if the arr [I] than TMP [0, 1]... k, record the position j 
} 
If (j & lt; K) {//if found j, the insert element 
For (int m=k - 1; M> j; M -) TMP [m]=TMP [m - 1);//j location after the move element back 
TMP [j]=arr [I]; 
} 
} 
Return TMP [k - 1); 
} 
} 

Time complexity, consider the worst case, it is the outer loop n times, the inner layer to find k times, move a k times, that is, n * 2 k

CodePudding user response:

reference 1st floor qybao response:

this is the most basic algorithm, give you an idea, the code is not wrote
Define a temporary array of length k TMP
Traverse the arr, arr [I] respectively with TMP [0, 1]... k, if is greater than the TMP element, then the arr [I] insert TMP, insert location elements were moving back (position is greater than k is automatically discarded), finally return to TMP [k] can
If the requirements cannot be repeated in the insert more than one step in the process of operation, is if TMP does not exist in the arr [I] is inserted, otherwise don't insert

I want to know, how to calculate the time complexity

CodePudding user response:

refer to the second floor qybao response:

write a simple, regardless of the repeated

 public class Sample {
Public static void main (String [] args) {
Try {
Int [] a={1,3,5,4,6,2}; 
Int m=findKth (a, 3); 
System. The out. Println (m); 

} the catch (Exception e) {
E.p rintStackTrace (); 
} 
} 

Public static int findKth (int [] arr, int k) {
If (k & gt; Arr. Length) return 0; 
Int [] TMP=new int [k].//define a long array k 
TMP [0]=arr [0]. 
int j=0; 
For (int I=1; ifor (j=0; jIf (arr [I] & gt; TMP [j]) break;//if the arr [I] than TMP [0, 1]... k, record the position j 
} 
If (j & lt; K) {//if found j, the insert element 
For (int m=k - 1; M> j; M -) TMP [m]=TMP [m - 1);//j location after the move element back 
TMP [j]=arr [I]; 
} 
} 
Return TMP [k - 1); 
} 
} 

Time complexity, consider the worst case, it is the outer loop n times, the inner layer to find k times, move a k times, that is, n * 2 k

How to calculate the time complexity