• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode81.搜索旋转排序数组II|SearchinRotatedSortedArrayII

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

  • This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
  • Would this affect the run-time complexity? How and why?

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

进阶:

  • 这是 搜索旋转排序数组 的延伸题目,本题中的 nums  可能包含重复元素。
  • 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?

12ms

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Bool {
 3         if nums.count == 0 {
 4             return false
 5         }
 6 
 7         var left = 0
 8         var right = nums.count - 1
 9 
10         while left < right {
11             let middle = left + (right - left) / 2
12             if nums[middle] == target {
13                 return true
14             }
15             if nums[middle] > nums[right] {
16                 if nums[middle] > target && nums[left] <= target {
17                     right = middle
18                 } else {
19                     left = middle + 1
20                 }
21             } else if nums[middle] < nums[right] {
22                 if nums[middle] < target && nums[right] >= target {
23                     left = middle + 1
24                 } else {
25                     right = middle
26                 }
27             } else {
28                 right -= 1
29             }
30         }
31 
32         return nums[left] == target
33     }
34 }

16ms

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Bool {
 3         
 4         if nums.count <= 0 { return false }
 5         
 6         var lo = 0
 7         var hi = nums.count - 1
 8         var mid = (lo + hi) / 2
 9 
10         while lo <= hi {
11             mid = (lo + hi) / 2
12             
13             //print("Check Piv [\(lo) \(mid) \(hi)] => {\(nums[lo]) \(nums[mid]) \(nums[hi])}")
14 
15             if nums[mid] == target {
16                 return true
17             }
18             
19             if nums[mid] > nums[lo] {
20                 
21                 if target >= nums[lo] && target < nums[mid] {
22                     hi = mid - 1
23                 } else {
24                     lo = mid + 1
25                 }
26             } else if nums[mid] < nums[lo] {
27                 if target > nums[mid] && target <= nums[hi] {
28                     lo = mid + 1
29                 } else {
30                     hi = mid - 1
31                 }
32             } else {
33                 lo += 1
34             }
35         }
36         return false
37     }
38 }

20ms

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

40ms

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Bool {
 3          var set: Set = Set<Int>.init()
 4         for d in nums {
 5             if d == target {
 6                 return true
 7             }else {
 8                 if set.contains(target) {
 9                     return true
10                 }else {
11                     set.insert(d)
12                 }
13             }
14         }
15         return false 
16     }
17 }

 

44ms

1 class Solution {
2     
3     func search(_ nums: [Int], _ target: Int) -> Bool {
4         return nums.contains(target)
5     }
6 }

52ms

 1 class Solution {
 2     func search(_ nums: [Int], _ target: Int) -> Bool {
 3         if nums.isEmpty
 4         {
 5             return false
 6         }
 7         
 8         var distinct = removeDuplicates(nums)
 9         
10         return searchRec(&distinct, target, start:0, end:distinct.count - 1)
11     }
12     
13     func searchRec(_ num: inout [Int], _ target: Int, start: Int, end: Int) -> Bool
14     {
15         if start == end
16         {
17             return num[start] == target
18         }
19         
20         let diff = end - start
21         let center = start + (diff - (diff % 2)) / 2
22         
23         if num[center] == target 
24         {
25             return true
26         }
27         
28         if num[start] <= num[center]
29         {
30             if target >= num[start] && target < num[center]
31             {
32                 return searchRec(&num, target, start:start, end:center - 1)
33             }
34             
35             return searchRec(&num, target, start:center + 1, end:end)
36         }
37         else if num[start] >= num[center]
38         {
39             if target >= num[start] || target < num[center]
40             {
41                 return searchRec(&num, target, start:start, end:center - 1)
42             }
43 
44             return searchRec(&num, target, start:center + 1, end:end)
45         }
46         
47         return false
48         
49     }
50     
51     func removeDuplicates(_ nums: [Int]) -> [Int]
52     {
53         if nums.isEmpty
54         {
55             return nums
56         }
57         
58         var distinct = [nums[0]]
59         var prev = nums[0]
60         
61         for val in nums[1..<nums.count]
62         {
63             if val != prev && val != nums[0]
64             {
65                 distinct.append(val)
66             }
67             
68             prev = val
69         }
70         
71         return distinct
72     }
73 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode1024.视频拼接|VideoStitching发布时间:2022-07-13
下一篇:
iOS-OC/Swift:验证手机号/固话用正则表达式发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap