欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

查找数组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];
        }
    }
}

 

上一篇:

下一篇: