溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

LeetCode如何解決在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置問(wèn)題

發(fā)布時(shí)間：2021-12-15 10:30:49 來(lái)源：億速云 閱讀：133 作者：小新 欄目：大數(shù)據(jù)

這篇文章將為大家詳細(xì)講解有關(guān)LeetCode如何解決在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置問(wèn)題，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。


 

題目描述

給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開(kāi)始位置和結(jié)束位置。

你的算法時(shí)間復(fù)雜度必須是 O(log n) 級(jí)別。

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

示例:

輸入: nums = [5,7,7,8,8,10], target = 8輸出: [3,4]
 
輸入: nums = [5,7,7,8,8,10], target = 6輸出: [-1,-1]
    

題目解析

題目中要求了時(shí)間復(fù)雜度為O(log n),這就很清楚要使用二分查找法了。

首先定義兩個(gè)指針變量，分別存儲(chǔ)左右兩個(gè)位置的索引。首先去找目標(biāo)值的最左面的索引,通過(guò)循環(huán)為了防止元素丟失,每次保留最右面的元素,左側(cè)的指針移動(dòng)時(shí)+1。在循環(huán)結(jié)束的時(shí)候判斷一下數(shù)組中是否包括目標(biāo)值,不包括的話直接退出。右面的跟左側(cè)相同，只不過(guò)正好相反。

代碼實(shí)現(xiàn)

// 34. 下一個(gè)排列// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/// 時(shí)間復(fù)雜度：O(n)// 空間復(fù)雜度：O(1)class Solution {    public int[] searchRange(int[] nums, int target) {		int[] res = new int[] { -1, -1 };		int left = 0;		int right = nums.length - 1;		int l = left;		int r = right;		while (left < right) {			int mid = (left + right) / 2;			if (nums[mid] < target) {				left = mid + 1;			} else {				right = mid;			}		}		if (left>right||nums[left]!=target) {			return new int[]{-1,-1};		}		while (l < r) {			int mid = (l + r) / 2 + 1;			if (nums[mid] > target) {				r = mid - 1;			} else {				l = mid;			}		}		if (left > right || left > r) {			return new int[] { -1, -1 };		} else {			return new int[] { left, r };		}	}}

關(guān)于“LeetCode如何解決在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置問(wèn)題”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手