在之前ARTS打卡中，我每次都把演算法、英文檔案、技巧都寫在一個文章里，這樣對我的幫助是挺大的，但是可能給讀者來說，一下子有這么多的輸入，還是需要長時間的消化，
那我現在改變下方式，將每一個模塊細分化，并且描述的更細致點，這樣就能和大家更好地交流，更好地探討具體的細節，也能讓大家更好地消化所學的知識，
所以，后續的ARTS打卡，會嘗試先將演算法以及英文檔案拆分開，11月，識訓的季節，讓我們繼續前行，在秋天識訓更多，學習更多，小編與你同行！
Algorithm LeetCode演算法
在排序陣列中查找元素的第一個和最后一個位置
(https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
題目描述：給定一個按照升序排列的整數陣列 nums，和一個目標值 target，找出給定目標值在陣列中的開始位置和結束位置，
你的演算法時間復雜度必須是 O(log n) 級別，
如果陣列中不存在目標值，回傳 [-1, -1]，
示例1：
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例2：
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
解法一：線性掃描法
因為這是一個簡單的一維陣列，我們要在陣列上進行查找，最笨的方法自然就是用常規的方法進行一個個遍歷查找，在這里我們叫他線性掃描，
首先，我們對輸入的陣列nums先從頭到尾進行遍歷，當遇到第一個目標數字target時中止遍歷，并記錄下所在的位置，如果沒有遇到數字，說明整個陣列都不存在該目標，則直接回傳一個找不到數字的結果即可，在這里就是 [-1,-1] ，
在找到第一個數字的前提下，我們從陣列的尾部往前遍歷，遇到第一個目標數字時，就是我們需要的第二個目標數字（因為最左邊有一個已經存在了，所以必然存在一個最右邊的數字不會產生找不到的情況），
最后，我們輸出結果即可，
/**
*
* @Title :
* @Description: 線性掃描
* @param nums
* @param target
* @return
* @return :int[]
* @throws
*/
public static int[] searchRange1(int[] nums, int target) {
int[] range = {-1,-1};
// 從頭到尾遍歷，先查找左邊的元素
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
range[0] = i;
break;
}
}
// 如果左邊的元素找到最后也沒找到，那么說明陣列里不存在此元素，直接回傳找不到的結果[-1,-1]
if (range[0] == -1) {
return range;
}
// 從尾到頭遍歷，繼續查找右邊的元素
for (int j = nums.length - 1; j >= 0 ; j--) {
if (nums[j] == target) {
range[1] = j;
break;
}
}
return range;
}
解法二：二分查找
為什么會想到用二分查找呢？因為給出的題目里描述了，我們傳入的陣列是已經排過序的，二分法能有效提高查找效率，
同樣的也是需要進行類似線性查找的方式，只不過這次我們查找的次數不會很多，首先，為了找到最左邊（或者最右邊）包含 target 的下標（而不是找到的話就回傳 true ），所以在我們找到一個 target 后不能馬上停止，我們需要繼續搜索，直到 lo == hi 且它們在某個 target 值處下標相同，
另一個改變是 left 引數的引入，它是一個 boolean 型別的變數，指示我們在遇到 target == nums[mid] 時應該做什么，如果 left 為 true ，那么我們遞回查詢左區間，否則遞回右區間，考慮如果我們在下標為 i 處遇到了 target ，最左邊的 target 一定不會出現在下標大于 i 的位置，所以我們永遠不需要考慮右子區間，當求最右下標時，道理同樣適用，
該方式參考力扣官方題解：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/，感興趣的同學可以鏈接過去學習下，
public static int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1,-1};
int leftIndex = searchIndex(nums, target,true);
if (leftIndex == nums.length || nums[leftIndex] != target) {
return targetRange;
}
targetRange[0] = leftIndex;
targetRange[1] = searchIndex(nums, target, false) - 1;
return targetRange;
}
// 遍歷左區間或者右區間
private static int searchIndex(int[] nums,int target,boolean left) {
int lo = 0;
int length = nums.length;
while (lo < length) {
int mid = (lo + length) / 2;
if (nums[mid] > target || (left && target == nums[mid])) {
length = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
在上一次長久養成的打卡習慣可千萬不能丟呀 還有一個系統介紹了二分法的文章，在這個題解里又做了一次介紹，對你的二分法會有深刻的理解，
所以，小編還是貼出地址來，https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/ 讓大家去學習下，在這里就不進行贅述了，怕描述錯了，達不到作者想要的效果，所以在此說聲抱歉啦，
寫了很久，這是一份適合普通大眾/科班/非科班的『學習路線』
長久養成的打卡習慣可千萬不能丟呀
Java 中的 final、finally、finalize 有什么不同？
求求你別再“從入門到放棄了”，貴在堅持
「奔跑吧攻城獅」感謝大家的關注，現在后臺回復「設計模式」贈你小編精心挑選設計模式書籍，小編想打造一個高質量交流群，回復「加群」或右下角點擊「撩我 -> 一起學」解鎖，
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57095.html
標籤：其他
下一篇：w10環境下Hexo博客搭建