无序数组求给定值是第K大的元素

共 3672字,需浏览 8分钟

 ·

2020-09-02 23:43


从今天起我将单独开设「码农题库」专栏,持续为大家分享总结各大厂的技术面试题及解题思路,并将对此进行分类汇总,形成海量免费题库,方便大家升职加薪!希望大家支持!今天先给大家分享一道来自字节跳动的算法面试作为开场!


“给定一个无序数组[2,3,6,5,1,7,8],求给定的元素是第K大的元素?”

示例:

例如输入:n=7,那么在这个数组中7是第6大的元素,所以K=6




这是一道非常常见的算法面试题,最近有朋友反馈在头条的面试中也遇到了这道题,今天就具体和大家聊聊这道题的解法以及它背后的算法知识。

从解法上看,主要思路如下:

“先将这个无序数组由小到大进行排序,然后在排好序的数组中查找给定元素的下标,而找到数组下标也就知道是第几大的元素了”。

但这也涉及,到底该采用何种排序算法,以及排序后如何查找给定元素的问题!而这将考察到候选人对于常用排序、查找算法知识的掌握情况。

先回顾下常用的排序算法,具体如下表所示:

以上表格总结了常见的排序算法及其算法复杂度情况,其中冒泡排序、鸡尾酒排序(冒泡排序的改进版)、选择排序、插入排序的时间复杂度都是O(n^2)指数级,所以如果采用此类算法来解答此题,即便在写对的情况下,面试官肯定也会继续问你有没有时间复杂度更低的解法。

所以要基本Get到本题考查的点,至少要采用快速排序、归并排序、堆排序或计数排序中的一种来实现数组的排序。而完成排序后如何在有序数组中查找指定元素,则需要根据常用的查找算法选择一种时间复杂度更低的。常用的查找算法有:


方法1:快速排序/二分查找

接下来我们以快速排序/二分查找的方式来解答下此题,代码如下:

public class OneDisorderArraySortAndFind {

    public static void main(String args[]) {
        int n = 5;
        int[] array = new int[]{2365178};
        //先对无序数组进行排序,得到有序数组
        quickSort(array, 0, array.length - 1);
        //二分查找
        int k = binarySearch(array, n) + 1;
        System.out.println("元素{" + n + "}是第" + k + "大的元素");
    }

    /**
     * 数组排序算法(快速排序)
     */

    public static void quickSort(int[] array, int startIndex, int endIndex) {
        //递归结束条件:startIndex大等于endIndex的时候
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素位置
        int pivotIndex = partition(array, startIndex, endIndex);
        //用分治法递归数例的两部分
        quickSort(array, startIndex, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, endIndex);
    }

    /**
     * 快速排序得到基准元素
     */

    private static int partition(int[] array, int startIndex, int endIndex) {
        //取第一个位置的元素作为基准元素
        int pivot = array[startIndex];
        int left = startIndex;
        int right = endIndex;
        //坑的位置,初始值等于pivot的位置
        int index = startIndex;
        //大循环在左右指针重合或者交错的时候结束
        while (right >= left) {
            //right指针从右向左进行比较
            while (right >= left) {
                if (array[right] < pivot) {
                    array[left] = array[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            }
            //left指针从左向右进行比较
            while (right >= left) {
                if (array[left] > pivot) {
                    array[right] = array[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        array[index] = pivot;
        return index;
    }

    /**
     * 查找算法-查找有序数组中的元素,返回数组下标(二分查找)
     */

    public static int binarySearch(int[] array, int target) {
        //查找范围起点
        int start = 0;
        //查找范围终点
        int end = array.length - 1;
        //查找范围中位数
        int mid;
        while (start <= end) {
            //mid=(start+end)/2 有可能溢出
            mid = start + (end - start) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }
}


方法2:堆排序/二分查找

快速排序算法在时间复杂度上并不固定,其平均时间复杂度是O(nlogn),但其最坏的情况下时间复杂度可能得到O(n^2)。所以我们还可以利用基于二叉堆的堆排序算法来解这道题,具体代码如下:

public class OneDisorderArraySortAndFind {

    public static void main(String args[]) {
        int n = 1;
        int[] array = new int[]{2365178};
        //堆排序
        heapSort(array);
        //二分查找
        int k = binarySearch(array, n) + 1;
        System.out.println("元素{" + n + "}是第" + k + "大的元素");
    }

    /**
     * 数组排序算法(堆排序)
     *
     * @param array
     */

    public static void heapSort(int[] array) {
        //1.把无序数组构建成二叉堆
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
        System.out.println(Arrays.toString(array));
        //2.循环删除堆顶元,移到集合尾部,调节堆产生新的堆顶
        for (int i = array.length - 1; i > 0; i--) {
            //最后一个元素和第一元素进行交换
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            //下沉调整最大堆
            downAdjust(array, 0, i);
        }
    }

    /**
     * 下沉调整
     *
     * @param array       待调整的堆
     * @param parentIndex 要下沉的父节点
     * @param length      堆的有效大小
     */

    private static void downAdjust(int[] array, int parentIndex, int length) {
        //temp保存父节点
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            //如果有右孩子,且右孩子大于左孩子的值,则定位到右孩子
            if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            //如果父节点小于任何一个孩子的值,直接跳出
            if (temp >= array[childIndex]) {
                break;
            }
            //无需真正交换,单向赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 查找算法-查找有序数组中的元素,返回数组下标(二分查找)
     *
     * @param array
     * @param target
     * @return
     */

    public static int binarySearch(int[] array, int target) {
        //查找范围起点
        int start = 0;
        //查找范围终点
        int end = array.length - 1;
        //查找范围中位数
        int mid;
        while (start <= end) {
            //mid=(start+end)/2 有可能溢出
            mid = start + (end - start) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    } 
}


上面提到的排序算法及二分查找法是计算机领域的基础算法,也是面试中经常考察到的点,所以要顺利通过面试,还需要多花时间真正掌握。但对于本题来说,排序会无端对不需要的查找的元素进行处理,所以在一定程度上增加了算法的消耗,其时间复杂度为O(nlogn)。

需要注意本题还会经常考到另外一种类型,具体如下:

"给定一个无序数组[2,3,6,5,1,7,8],求第K大的元素?"

示例:

例如输入:k=1,那么在这个数组中8是第1大的元素,所以K=1的结果是8


大家可以思考下如果换成这种问法,那么除了排序法外,是否还有更好的解法?


—————END—————


来源:字节跳动 | 分类:算法 | 难度:中等 | 频率:高


浏览 21
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报