溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關LeetCode如何解決在排序數組中查找元素的第一個和最后一個位置問題，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
你的算法時間復雜度必須是 O(log n) 級別。
如果數組中不存在目標值，返回 [-1, -1]。
示例:
輸入: nums = [5,7,7,8,8,10], target = 8輸出: [3,4]
輸入: nums = [5,7,7,8,8,10], target = 6輸出: [-1,-1]
題目中要求了時間復雜度為O(log n),這就很清楚要使用二分查找法了。
首先定義兩個指針變量，分別存儲左右兩個位置的索引。首先去找目標值的最左面的索引,通過循環為了防止元素丟失,每次保留最右面的元素,左側的指針移動時+1。在循環結束的時候判斷一下數組中是否包括目標值,不包括的話直接退出。右面的跟左側相同，只不過正好相反。
// 34. 下一個排列// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/// 時間復雜度：O(n)// 空間復雜度：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 };}}}
關于“LeetCode如何解決在排序數組中查找元素的第一個和最后一個位置問題”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
