查找数组arr中第k小的奇数,如果不存在则返回0
程序员文章站
2024-01-08 23:02:34
...
/** * @author niuxd * @title: Test * @date 2020/7/14 12:45 */ public class Test { public static void main(String[] args) { int[] arr = {6, 9, 1, 5, 9, 4, 2}; //查找第k小的奇数 String kStr = "2"; int k ; try{ k=Integer.parseInt(kStr); if(k<=0){ System.out.println("参数k应为正整数"); System.exit(-1); } //如果参数k超过数组长度,需要返回值,可以注释掉这几行 if(k>arr.length){ System.out.println("参数k超过数组长度"); System.exit(-1); } Test test = new Test(); int number = test.findKth(arr, k); System.out.println("第"+k+"小的数是:"+number); }catch (ArrayIndexOutOfBoundsException aioe){ System.out.println("请输入参数k"); System.exit(-1); }catch (NumberFormatException nfe){ System.out.println("参数k应为正整数"); System.exit(-1); } } /** * 查找数组arr中第k小的奇数,如果不存在则返回0 * @param array 数组 * @param k 第k位 * @return */ private int findKth(int[] array, int k) { //1、先进行排序,二分法,复杂度为O(nlogn) mergeSort(array, 0, array.length - 1); //2、查找第k小的数 //index用于计数,第几个数值 int index = 1; for (int i = 0;i<array.length;i++){ //找奇数 if (array[i]%2!=0){ //找到第k小/大的数据则返回 if (index==k){ return array[i]; } //继续查找直至第k小/大 index++; } } //3、没找到返回 0 return 0; } /** * 通过二分法进行排序 */ public void mergeSort(int[] array, int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(array, left, mid); mergeSort(array, mid + 1, right); merge(array, left, mid, right); } /** * 分为一组一组进行对比,放入临时容器中,排序完成后更新数组 */ private void merge(int[] array, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int leftPos = left; int rightPos = mid + 1; int tempPos = 0; while (leftPos <= mid && rightPos <= right) { if (array[leftPos] <= array[rightPos]) { temp[tempPos++] = array[leftPos++]; } else { temp[tempPos++] = array[rightPos++]; } } if (leftPos > mid) { while (rightPos <= right) { temp[tempPos++] = array[rightPos++]; } } else { while (leftPos <= mid) { temp[tempPos++] = array[leftPos++]; } } for (int i = 0; i < temp.length; i++) { array[i + left] = temp[i]; } } }