[Letcode]第[34]题[JAVA][在排序数组中查找元素的第一个和最后一个位置][暴力][二分]

心已赠人 2023-03-01 05:45 6阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 线性扫描（不符合题意） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int[] searchRange(int[] nums, int target) { 
            int[] targetRange = { -1, -1};
    
            // find the index of the leftmost appearance of `target`.
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] == target) { 
                    targetRange[0] = i;
                    break;
                }
            }
    
            // if the last loop did not find any index, then there is no valid range
            // and we return [-1, -1].
            if (targetRange[0] == -1) { 
                return targetRange;
            }
    
            // find the index of the rightmost appearance of `target` (by reverse
            // iteration). it is guaranteed to appear.
            for (int j = nums.length-1; j >= 0; j--) { 
                if (nums[j] == target) { 
                    targetRange[1] = j;
                    break;
                }
            }
    
            return targetRange;
        }
    }

###### 2. 二分法（排除法） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

如果是找第 1 次出现的下标，先想到 nums\[mid\] < target 有一方面的原因是，找第 1 次出现的下标，是找靠左的元素，所以就得按照 →→→→→→ 这个方向去逼近。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

如果是找最后 1 次出现的下标，是找靠右的元素，所以就得按照 ◀️◀️◀️◀️◀️◀️ 这种方式去逼近。其实完全可以分析得再细一点，就看 ==、> 和 < 的情况，下一轮搜索的区间在那里，可能更具体一些。

**时间复杂度：O(N) 空间复杂度：O(1)**

public class Solution { 
        public int[] searchRange(int[] nums, int target) { 
            int len = nums.length;
            if (len == 0) { 
                return new int[]{ -1, -1};
            }
    
            int firstPosition = findFirstPosition(nums, target);
            if (firstPosition == -1) { 
                return new int[]{ -1, -1};
            }
    
            int lastPosition = findLastPosition(nums, target);
            return new int[]{ firstPosition, lastPosition};
        }
    
        private int findFirstPosition(int[] nums, int target) { 
            int left = 0;
            int right = nums.length - 1;
            while (left < right) { 
                int mid = (left + right) >>> 1;
                // 小于一定不是解
                if (nums[mid] < target) { 
                    // 下一轮搜索区间是 [mid + 1, right]
                    left = mid + 1;
                } else { 
                    right = mid;
                }
            }
    
            if (nums[left] == target) { 
                return left;
            }
            return -1;
        }
    
        private int findLastPosition(int[] nums, int target) { 
            int left = 0;
            int right = nums.length - 1;
            while (left < right) { 
                int mid = (left + right + 1) >>> 1;
                // 大于一定不是解
                if (nums[mid] > target) { 
                    // 下一轮搜索区间是 [left, mid - 1]
                    right = mid - 1;
                } else { 
                    left = mid;
                }
            }
            return left;
        }
    }

#### 【总结】 ####

###### 1.[\[算法\]\[二分查找\]\[排除法\]总结][Link 1] ######

###### 2. 搜索区间问题 ######

*  如果是找第 1 次出现的下标，先想到 nums\[mid\] < target 有一方面的原因是，找第 1 次出现的下标，是找靠左的元素，所以就得按照 →→→→→→ 这个方向去逼近。
 *  如果是找最后 1 次出现的下标，是找靠右的元素，所以就得按照 ◀️◀️◀️◀️◀️◀️ 这种方式去逼近。其实完全可以分析得再细一点，就看 ==、> 和 < 的情况，下一轮搜索的区间在那里，可能更具体一些。

###### 3. 出现 left = mid 记得取中间值要 mid = (left + right + 1) >>> 1，避免死循环 ######

参考链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/si-lu-hen-jian-dan-xi-jie-fei-mo-gui-de-er-fen-cha/

参考链接：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-/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/78daed3ebc2b481784f58f45886728aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/58c594de90134987a42d0a75e57cf6c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230209/58fbbd8b4faf40bfa336819a532964bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20230209/81f870fa69d4483281f9775e8169f3aa.png
[Link 1]: https://blog.csdn.net/dadongwudi/article/details/105345157