快捷導航

Java在排序數(shù)組中查找元素的第一個和最后一個位置的方法詳解

更新時間：2024年01月18日 11:57:05 作者：楠枬

相信大家在操作Java的時候經(jīng)常會要在一個數(shù)組(無序)中查找元素的第一個和最后一個位置,下面這篇文章主要給大家介紹了關(guān)于Java在排序數(shù)組中查找元素的第一個和最后一個位置的相關(guān)資料,需要的朋友可以參考下

一、題目描述

給你一個按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個目標值 target。請你找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標值 target，返回 [-1, -1]。

你必須設(shè)計并實現(xiàn)時間復雜度為 O(log n) 的算法解決此問題。

示例：

輸入：nums = [5,7,7,8,8,10]，target = 8

輸出：[3, 4]

輸入：nums = [5,7,7,8,8,10]，target = 6

輸出：[-1, -1]

輸入：nums = [ ]，target = 0

輸出：[-1, -1]

二、題解

思路分析：

題目要求我們找到出現(xiàn)target的第一個位置和最后一個位置，首先，我們想到可以通過暴力枚舉的方法來解決該問題，即遍歷數(shù)組，并記錄target第一次出現(xiàn)和最后一次出現(xiàn)的位置。然而，題目要求我們實現(xiàn)時間復雜度為O(log n)的算法，且題目中給出的數(shù)組為非遞減的數(shù)組，因此，我們可以考慮使用二分查找的方法來解決該問題

由于題目中數(shù)據(jù)量較小，使用遍歷的方法也可以通過該題

遍歷代碼：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1;
        int last = -1;
        boolean flg = false;//判斷是否是第一個位置
        for (int i = 0; i < nums.length; i++) {
            //第一個位置
            if(nums[i] == target && !flg){
                first = i;
                flg = true;
            }
            //最后一個位置
            //注意處理特殊情況，即最后一個元素在最后一個位置時，nums[i+1]越界
           if(nums[i] == target && (i == nums.length - 1 || nums[i+1] != target)){
                last = i;
            }
        }
        int[] ret = {first,last};
        return ret;
    }
}

如何使用二分查找來解決該問題？

題目要求我們找到target在數(shù)組中第一次出現(xiàn)和最后一次出現(xiàn)的位置，利用數(shù)組非遞減的性質(zhì)

首先我們查找元素的第一個位置：

我們可通過target將數(shù)組分為兩部分：

其中，左邊部分為小于target的元素，右邊部分為大于等于target的元素，由于右邊區(qū)域大于等于target，因此右邊區(qū)域最左邊的值即為target第一次出現(xiàn)的位置，即右邊區(qū)域的左端點為所求結(jié)果

我們定義left指向0位置，right指向最后一個元素，mid指向中間位置

若mid指向的元素落在右邊區(qū)間，此時nums[mid]大于等于target，需要更新right的值，由于要找的結(jié)果（target第一次出現(xiàn)的位置）在此區(qū)間內(nèi)，即mid所指向的位置可能就是最終結(jié)果，因此不能將right更新為mid - 1，而應(yīng)更新為mid

若mid所指向的元素落在左邊區(qū)間，此時nums[mid]小于target，需要更新 left 的值，由于要找的結(jié)果不在此區(qū)間內(nèi)，因此可將left的結(jié)果更新為 mid + 1

當left和right之間元素為偶數(shù)個時，此時中間元素有兩個，應(yīng)該選擇哪一個作為中間元素？

由于我們查找的是右邊區(qū)間內(nèi)最左邊的元素，因此，應(yīng)該選擇左邊的元素作為中間元素

若選擇右邊元素作為中間元素，能夠成功查找到結(jié)果嗎？

當選擇右邊元素作為中間元素時，此時會出現(xiàn)死循環(huán)的情況，例如：

上圖中，當選擇右邊元素作為中間元素時，mid指向的元素落在右邊區(qū)間，此時將right更新為mid，再求mid，此時mid仍為指向剛才位置，即落在右邊區(qū)間，此時再次更新right為mid，再次求mid... 從而死循環(huán)

循環(huán)條件如何設(shè)置？

由于我們將right更新為mid，因此循環(huán)的條件應(yīng)為left < right，若循環(huán)條件設(shè)置為left <= right，當left = right時，此時找到結(jié)果，而結(jié)果落在右邊區(qū)間，此時會更新right的值，而right 更新為mid，即當前位置，從而死循環(huán)

分析完以上問題后，我們可以嘗試編寫查找右邊區(qū)域最左邊元素的代碼：

//查找target第一次出現(xiàn)的位置(右邊區(qū)間的左端點)
int left = 0,right = nums.length - 1,mid = left + (right - left)/2;
//循環(huán)條件應(yīng)設(shè)置為left < right 
//不能設(shè)置為left <= right，否則會死循環(huán)
while(left < right){
    //當mid所指向的元素落在左邊區(qū)間時，更新left
    if(nums[mid] < target){
        left = mid + 1;
    }else{//當mid所指向的元素落在右邊區(qū)間時，此時更新right
        //由于右邊區(qū)間的元素大于等于target，即結(jié)果在該區(qū)間內(nèi)，
        // 因此不能將right更新為mid - 1,而應(yīng)更新為mid
        right = mid;
    }
    //更新mid，當有兩個中間元素時，mid應(yīng)指向其中左邊的元素
    mid = left + (right - left) / 2;
}

此時我們查找target最后一次出現(xiàn)的位置

與查找第一次出現(xiàn)位置的思路相同，我們首先將數(shù)組分為兩個部分：

其中，左邊區(qū)間內(nèi)元素小于等于target，右邊區(qū)間元素大于target

此時，要找的結(jié)果即為左邊區(qū)間的右端點

同樣的，定義left指向0位置，right指向最后一個元素，mid指向中間位置

若mid所指向的元素落在左邊區(qū)間，此時需要更新left的值，由于要找的結(jié)果落在此區(qū)間內(nèi)，即mid所指向的位置可能就是最終結(jié)果，因此不能將left更新為mid + 1，而應(yīng)更新為mid

若mid所指向的元素落在右邊區(qū)間，此時需要更新right的值，由于要找的結(jié)果不在右邊區(qū)間，因此可將right的值更新為mid - 1

當left和right之間元素為偶數(shù)個時，此時中間元素有兩個，應(yīng)該選擇哪一個作為中間元素？

由于我們查找的是左邊區(qū)間內(nèi)最右邊的元素，因此，應(yīng)該選擇右邊的元素作為中間元素

即 mid = left + (right - left + 1) / 2;

同樣的，當選擇左邊元素作為中間元素時，也會造成死循環(huán)

此時left的值一直更新為當前位置，造成死循環(huán)

循環(huán)條件的設(shè)置：

循環(huán)條件也同樣應(yīng)該設(shè)置為left < right，否則會死循環(huán)

此時我們嘗試編寫查找左邊區(qū)間右端點代碼：

//查找區(qū)間右端點
left = mid;
right = nums.length - 1;
mid = left + (right - left + 1)/2;
while(left < right){
    //當mid所指向的值落在右邊區(qū)域時，更新右端點
    if(nums[mid] > target){
        right = mid - 1;
    }else{//當mid所指向的值落在左邊區(qū)域時，更新左端點
        //由于左邊區(qū)間的元素小于等于target，即結(jié)果在該區(qū)間內(nèi)，
        //因此不能將left更新為mid + 1,而應(yīng)更新為mid
        left = mid;
    }
    //更新mid的值，若有兩個中間元素時，mid應(yīng)指向其中右邊的元素
    mid = left + (right - left + 1) / 2;
}

完整代碼：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1,-1};
         //若數(shù)組為空，直接返回ret
        if(nums.length == 0){
            return ret;
        }
        //查找target第一次出現(xiàn)的位置(右邊區(qū)間的左端點)
        int left = 0,right = nums.length - 1,mid = left + (right - left) / 2;
        //循環(huán)條件應(yīng)設(shè)置為left < right
        //不能設(shè)置為left <= right，否則會死循環(huán)
        while(left < right){
            //當mid所指向的元素落在左邊區(qū)間時，更新left
            if(nums[mid] < target){
                left = mid + 1;
            }else{//當mid所指向的元素落在右邊區(qū)間時，此時更新right
                //由于右邊區(qū)間的元素大于等于target，即結(jié)果在該區(qū)間內(nèi)，
                // 因此不能將right更新為mid - 1,而應(yīng)更新為mid
                right = mid;
            }
            //更新mid，當有兩個中間元素時，mid應(yīng)指向其中左邊的元素
            mid = left + (right - left) / 2;
        }
        //此時left = right = mid,使用哪一個變量進行判斷和更新都可以
        //若數(shù)組中無值為target的元素，直接返回ret
        if(nums[left] == target){
            ret[0] = left;
        }else{
            return ret;
        }

        //查找區(qū)間右端點
        left = mid;
        right = nums.length - 1;
        mid = left + (right - left + 1)/2;
        while(left < right) {
            //當mid所指向的值落在右邊區(qū)域時，更新右端點
            if (nums[mid] > target) {
                right = mid - 1;
            } else {//當mid所指向的值落在左邊區(qū)域時，更新左端點
                //由于左邊區(qū)間的元素小于等于target，即結(jié)果在該區(qū)間內(nèi)，
                //因此不能將left更新為mid + 1,而應(yīng)更新為mid
                left = mid;
            }
            //更新mid的值，若有兩個中間元素時，mid應(yīng)指向其中右邊的元素
            mid = left + (right - left + 1) / 2;
        }
        ret[1] = left;
        return ret;
    }
}

題目來自：

34. 在排序數(shù)組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）