티스토리 뷰
[LeetCode] 34번 - Find First and Last Position of Element in Sorted Array [Swift]
Dev_Pingu 2021. 1. 22. 23:31문제 링크
Find First and Last Position of Element in Sorted Array - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Follow up: Could you write an algorithm with O(log n) runtime complexity?
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]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums is a non-decreasing array.
- -109 <= target <= 109
문제 풀이
이 문제는 정수형 배열 1개와 target이라는 정수 하나가 주어집니다.
정수형 배열은 오름차순으로 정렬 되어 있는데, 이 배열에서 target의 index의 시작점과 끝점을 찾아내는 것이 목표입니다.
일단 정렬된 정수 배열에서 특정 값을 빠르게 찾을 수 있는 방법 중 하나는 이분 탐색이라는 방법이 있습니다!
저는 이분 탐색을 사용하여 target 값을 일단 찾은 뒤 그 위치의 앞뒤를 하나씩 늘려나가며 정답을 찾았습니다.
예를 들어 예제에서 주어진 [5,7,7,8,8,10] 에서 8을 찾는 문제일 때 이분 탐색을 사용하면 8을 index = 3에서 찾게 될텐데 index+1, index-1 값을 확인하고 target과 같으면 범위를 늘리고 taeget과 다르다면 그대로 두는 방법을 반복하여 문제를 해결했습니다.
소스 코드
class Solution {
func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
if nums.count == 0 {
return [-1,-1]
}
var left: Int = 0
var mid: Int = nums.count / 2
var right: Int = nums.count - 1
while left <= right {
if nums[mid] == target {
break
} else if nums[mid] < target {
left = mid + 1
mid = (left + right) / 2
} else if nums[mid] > target {
right = mid - 1
mid = (left + right) / 2
}
}
if left > right {
return [-1,-1]
}
var min: Int = mid
var max: Int = mid
var findMin: Bool = false
var findMax: Bool = false
while !(findMin && findMax) {
if min - 1 >= 0 {
if !findMin && nums[min - 1] == target {
min -= 1
} else if !findMin && nums[min - 1] != target {
findMin = true
}
} else {
findMin = true
}
if max + 1 <= nums.count - 1{
if !findMax && nums[max + 1] == target {
max += 1
} else if !findMax && nums[max + 1] != target {
findMax = true
}
} else {
findMax = true
}
}
return [min,max]
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 39번 - Combination Sum [Swift] (0) | 2021.01.27 |
---|---|
[LeetCode] 53번 - Maximum Subarray [Swift] (0) | 2021.01.22 |
[LeetCode] 20번 - Valid Parentheses [Swift] (0) | 2021.01.22 |
[LeetCode] 17번 - Letter Combination of a Phone Number [Swift] (0) | 2021.01.20 |
[LeetCode] 11번 - Container With Most Water [Swift] (0) | 2021.01.14 |
- Total
- Today
- Yesterday
- Combine
- Publisher
- 앱개발
- 아이폰
- OSTEP
- mac
- 문법
- operating
- 자료구조
- DP
- 테이블뷰
- Swift
- 프로그래밍
- 알고리즘
- OS
- 스위프트
- operator
- BFS
- 코딩테스트
- System
- pattern
- dfs
- Apple
- document
- 코테
- 백준
- IOS
- Xcode
- design
- 동시성
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |