美文网首页
二分查找(六)——无序数组也能二分查找?

二分查找(六)——无序数组也能二分查找?

作者: 旺叔叔 | 来源:发表于2018-09-26 16:31 被阅读0次

LeetCode_215_KthLargestElementinanArray

题目分析:

您还记得当年写过的快排吗?虽然不是最快的思路,确是本题的初衷。利用快排的操作,将问题分治。

解法:

public static int findKthLargest(int[] nums, int k) {
    int left = 0, right = nums.length - 1;
    while (true){
        int pos = partition(nums, left, right);
        if(k - 1 == pos) return nums[pos];
        else if(pos > k - 1) right = pos - 1;
        else left = pos + 1;
    }
}

public static int partition(int[] nums, int left, int right){
    int pivot = nums[left], l = left +1, r = right;
    while (l <= r){
        if(nums[l] < pivot && nums[r] > pivot)
            swap(nums, l, r);
        if (nums[r] <= pivot) r--;
        if (nums[l] >= pivot) l++;
    }
    swap(nums, left, r);

    return r;
}

public static void swap(int nums[], int left, int right){
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

相关文章

  • 二分查找(六)——无序数组也能二分查找?

    LeetCode_215_KthLargestElementinanArray 题目分析: 解法:

  • Java数据结构和算法(有序数组和二分查找)

    一、概述 有序数组中常常用到二分查找,能提高查找的速度。今天,我们用顺序查找和二分查找实现数组的增删改查。 二、有...

  • 查找算法

    参考资料 有序查找 二分查找 循环版 递归版 无序查找 顺序查找

  • day13

    查找算法 顺序查找 二分查找 差值查找 斐波那契查找 二分查找 前提数组必须是有序的。 升级 Interpolat...

  • 查找

    顺序查找 二分查找 插值查找 查找子数组最大和

  • 二分法查找

    二分法查找的前提是数组必须排序!!!二分法查找的前提是数组必须排序!!!二分法查找的前提是数组必须排序!!!二分法...

  • 二分查找

    二分查找 什么是二分查找 实现原理 什么是二分查找 二分查找是从一个有序数组中找到目标元素(通常是找下标)的过程 ...

  • 二分查找法

    在有序数组中,查找特定元素的方法有许多种,今天和大家分享的是二分查找法,二分查找法,也可以称为对半查找,折半查找,...

  • 数据结构和算法--二分查找

    二分查找 二分查找的思想 二分查找(Binary Search)算法,也叫折半查找算法。 二分查找针对的是一个有序...

  • Objective-C实现二分查找和插值查找

    二分查找二分查找 又称折半查找,要求数组必须是有序的数列,是一种有序查找算法。二分查找的时间复杂度是O(log n...

网友评论

      本文标题:二分查找(六)——无序数组也能二分查找?

      本文链接:https://www.haomeiwen.com/subject/xscjoftx.html