[Swift]LeetCode34.在排序数组中查找元素的第一个和最后一个位置|FindFirstandLastPos ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

[Swift]LeetCode34.在排序数组中查找元素的第一个和最后一个位置|FindFirstandLastPos ...

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9900149.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

给定一个按照升序排列的整数数组 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]

【二进制搜索】

直觉

因为数组已排序，我们可以使用二进制搜索来定位最左边和最右边的索引。

算法

除了用于查找最左侧和最右侧索引本身的子例程之外，整体算法与线性扫描方法的工作方式非常相似。在这里，我们使用修改后的二进制搜索来搜索已排序的数组，并进行一些小的调整。首先，因为我们正在找到最左边（或最右边）的索引target（而不是返回true我们找到的iff target），所以算法一找到匹配就不会终止。相反，我们继续搜索，直到lo == hi它们包含一些target可以找到的索引。

另一个变化是引入left参数，这是一个布尔值，表示在事件中要做什么target == nums[mid]; 如果 left是true，那么我们在关系上的左子阵列上“递归”。否则，我们走对了。要了解为什么这是正确的，请考虑我们target在索引处找到的情况 i。最左边target不能出现任何大于的索引i，因此我们永远不需要考虑正确的子阵列。相同的参数适用于最右边的索引。

下面的第一个动画显示了查找最左侧索引的过程，第二个动画显示了查找最右侧索引的索引右侧的过程。

68ms

 1 class Solution {
 2     func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
 3         var targetRange:[Int] = [-1, -1]
 4         var leftIdx:Int = extremeInsertionIndex(nums, target, true)
 5         
 6         // 声明`leftIdx` 在数组的边界内并且是 `target`
 7         // 实际上在`nums`中
 8         if leftIdx == nums.count || nums[leftIdx] != target
 9         {
10             return targetRange
11         }
12         
13         targetRange[0] = leftIdx
14         targetRange[1] = extremeInsertionIndex(nums, target, false) - 1
15         
16         return targetRange
17     }
18     
19     // 返回 `target`应该是最左边(或最右边)的索引
20     // 通过二进制搜索插入排序数组'nums'.
21     func extremeInsertionIndex(_ nums: [Int], _ target: Int,_ left:Bool) -> Int
22     {
23         var lo:Int = 0
24         var hi:Int = nums.count
25         
26         while (lo < hi)
27         {
28             var mid:Int = (lo + hi) / 2
29             if nums[mid] > target || (left && target == nums[mid])
30             {
31                 hi = mid
32             }
33             else
34             {
35                 lo = mid+1
36             }
37         }
38         return lo
39     }
40 }

12ms

 1 class Solution {
 2     func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
 3         let start = binarySearch(nums, target)
 4 
 5         if start == nums.count || nums[start] != target {
 6             return [-1, -1]
 7         }
 8 
 9         let end = binarySearch(nums, target + 1) - 1
10 
11         return [start, end]
12     }
13 
14     private func binarySearch(_ nums: [Int], _ target: Int) -> Int {
15         var left = 0
16         var right = nums.count
17 
18         while left < right {
19             let middle = left + (right - left) / 2
20             if nums[middle] < target {
21                 left = middle + 1
22             } else {
23                 right = middle
24             }
25         }
26 
27         return left
28     }
29 }

16ms

 1 class Solution {
 2     func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
 3         var left = 0
 4     var right = nums.count - 1
 5     var mid = 0
 6     var first = -1
 7     
 8     // 寻找第一个出现target的位置
 9     while left <= right {
10         mid = left + (right - left)/2
11         if nums[mid] >= target {
12             right = mid - 1
13         } else {
14             left = mid + 1
15         }
16         if nums[mid] == target {
17             first = mid
18         }
19     }
20     
21     // 如果找不到第一个直接返回
22     if first == -1 {
23         return [first ,first]
24     }
25     
26     // 寻找最后一个出现target的位置
27     var last = -1
28     left = first
29     right = nums.count - 1
30     while left <= right {
31         mid = left + (right - left)/2
32         if nums[mid] > target {
33             right = mid - 1
34         } else {
35             left = mid + 1
36         }
37         if nums[mid] == target {
38             last = mid
39         }
40     }
41     return [first,last]
42     }
43 }

16ms

 1 class Solution {
 2     func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
 3         
 4         if nums.count == 1
 5         {
 6             if nums[0] == target
 7             {
 8                 return [0,0]
 9             }
10             else{
11                 return [-1,-1]
12             }
13         }
14         var index = binarySearch(nums,0,nums.count-1,target)
15         print(index)
16         if index == -1
17         {
18             return [-1,-1]
19         }
20         let midIndex = index
21         var keepGoing = true
22         var startIndex = midIndex
23         while keepGoing
24         {
25             index -= 1
26             if index  >= 0
27             {
28                 if nums[index] == target
29                 {
30                     print("here")
31                     startIndex = index
32                 }
33                 else{
34                     keepGoing = false
35                 }
36             }else{
37                 keepGoing = false
38             }
39         }
40         
41           keepGoing = true
42         var endIndex = midIndex
43         while keepGoing
44         {
45             index += 1
46             if index  < nums.count
47             {
48                 if nums[index] == target
49                 {
50                     print("here2")
51                     endIndex = index
52                 }
53                 else{
54                     keepGoing = false
55                 }
56             }
57             else{
58                 keepGoing = false
59             }
60         }
61       
62         return [startIndex,endIndex]
63     }
64     
65     func binarySearch(_ nums:[Int],_ lo:Int,_ hi:Int,_ target:Int)->Int
66     {
67           if lo == hi
68         {
69             if nums[lo] == target
70             {
71                 return lo
72             }
73             else{
74                 return -1
75             }
76         }
77         if lo < hi
78         {
79             var mi = (lo+hi)/2
80             
81             if nums[mi] == target
82             {
83                 return mi
84             }
85             else if target < nums[mi]
86             {
87                 return binarySearch(nums,lo,mi-1,target)
88             }
89             else if target > nums[mi]
90             {
91                 return binarySearch(nums,mi+1,hi,target)
92             }
93         }
94         return -1
95     }
96 }

76ms

 1 class Solution {
 2     func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
 3         var startIndex: Int?
 4         var endIndex: Int?
 5         
 6         for (index, num) in nums.enumerated() {
 7             if num == target {
 8                 if startIndex == nil {
 9                     startIndex = index
10                 }
11                 
12                 endIndex = index
13             }
14         }
15         
16         if startIndex == nil {
17             return [-1, -1]
18         } else {
19             return [startIndex!, endIndex!]
20         }
21     }
22 }

104ms

 1 class Solution {
 2     func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
 3         var min = -1
 4         var max = -1
 5         for i in 0..<nums.count {
 6             guard nums[i] == target else {
 7                 continue
 8             }
 9             if min == -1 {
10                 min = i
11             }
12             max = i
13         }
14         return [min, max]
15     }
16 }