[每日一道小算法（七十九）][数组]查找数组中第k小的奇数

ゝ一纸荒年。 2023-07-12 05:22 25阅读 0赞

前言：  
今天投递了一份简历，面试官让先做一道题，就是查找数组中第k小的奇数。

### 题目描述 ###

查找数组arr（arr\[i\]>0,i>=0）中第k大的奇数，如果不存在则返回0，并计算出时间复杂度，不能使用库函数或者脚本中已经实现好的排序算法和工具，需要自己实现数据结构和所需要的算法；  
格式：public int findKth(int\[\] arr,int k)\{  
// 代码  
\}

### 解题思路 ###

既然不能是Java自带的排序函数，那么就自己实现一个排序函数吧。这里实现采用的Java的归并排序，比较稳定。时间复杂度是O（nlogn）。  
具体实现思路：就是先排序，排序好后遍历待排序序列然后找第K小的数

### 代码样例 ###

package com.asong.leetcode.AfterKQ;
    
    import java.util.Scanner;
    
    public class Solution { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            Solution solution = new Solution();
            while (scanner.hasNext())
            { 
                int n = scanner.nextInt();
                int k = scanner.nextInt();
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) { 
                    arr[i] = scanner.nextInt();
                }
                int result = solution.findKth(arr,k);
                System.out.println(result);
            }
        }
    
        /** * 采用归并排序 时间复杂度为O（nlogn） 稳定的排序 * @param arr * @param k * @return */
        public int findKth(int[] arr,int k)
        { 
            if(arr==null||k>arr.length)
            { 
                return 0;
            }
            sort(arr);
            if((arr[k-1]%2==1))
            { 
                    return arr[k-1];
            }
            
            return 0;
        }
    
        public void sort(int[] array)
        { 
            MergerSort(array,0,array.length-1);
        }
        public void MergerSort(int[] array,int low,int high)
        { 
            //递归结束条件
            if(low==high)
            { 
                return;
            }
            int mid = low + ((high-low)>>1);
            MergerSort(array,low,mid);
            MergerSort(array,mid+1,high);
            Merger(array,low,mid,high);
        }
        public void Merger(int[] array,int low,int mid,int high)
        { 
            //建立一个辅助空间
            int[] temp = new int[high-low+1];
            int index = 0;
            int p1 = low;
            int p2 = mid+1;
            while (p1<=mid&&p2<=high)
            { 
                if(array[p1]<=array[p2])
                { 
                    temp[index++] = array[p1++];
                }else { 
                    temp[index++] = array[p2++];
                }
            }
            while(p1<=mid)
            { 
                temp[index++] = array[p1++];
            }
            while (p2<=high)
            { 
                temp[index++] = array[p2++];
            }
            for (int i = 0; i < index; i++) { 
                array[low+i] = temp[i];
            }
        }
    }