//
// M_162_FindPeakElement.swift
// AlgorithmLeetCode
//
// Created by okerivy on 2017/3/9.
// Copyright ? 2017年 okerivy. All rights reserved.
// https://leetcode.com/problems/find-peak-element
import Foundation
// MARK: - 題目名稱: 162. Find Peak Element
/* MARK: - 所屬類別:
標(biāo)簽: Array, Binary Search
相關(guān)題目:
*/
/* MARK: - 題目英文:
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
click to show spoilers.
Note:
Your solution should be in logarithmic complexity.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
*/
/* MARK: - 題目翻譯:
峰值元素是大于其鄰居的元素。
給定一個輸入數(shù)組中的num[i] ≠ num[i+1]，找到一個元素并返回它的下標(biāo)。
該數(shù)組可能包含多個峰值，在這種情況下返回索引的任何一個峰是可以的。
你可以認(rèn)為 num[-1] = num[n] = -∞
例如，在數(shù)組[1, 2, 3, 1]中，3是一個峰值元素，你的函數(shù)應(yīng)該返回索引數(shù)2。
注：
你的解決方案應(yīng)該是對數(shù)復(fù)雜度。
信用:
特別感謝@ TS添加這個問題，并創(chuàng)建所有的測試用例。
*/
/* MARK: - 解題思路:
num[i] ≠ num[i+1] num[-1] = num[n] = -∞
這兩句話是關(guān)鍵
這題要求我們在一個無序的數(shù)組里面找到一個peak元素，所謂peak，就是值比兩邊鄰居大就行了。
對于這題，最簡單地解法就是遍歷數(shù)組，只要找到第一個元素，大于兩邊就可以了，復(fù)雜度為O(N)。
但這題還可以通過二分來做。
首先我們找到中間節(jié)點mid，如果大于兩邊返回當(dāng)前index就可以了, 讓 mid 和mid+1 進行比較
1, 如果 num[mid] < num[mid+1] 那么說明 peak 在右邊,因為 num[n] = -∞
也就是說 num[mid] < num[mid+1] > num[n]
這時候 low = mid+1 重新計算得到mid 繼續(xù)查找
1,
如果 num[mid] < num[mid+1] 那么說明 peak 在右邊,因為 num[n] = -∞
也就是說 num[mid] < num[mid+1] > num[n]
這時候 low = mid+1 重新計算得到mid 繼續(xù)查找
2,
如果 num[mid] > num[mid+1] 那么說明 peak 在左邊
因為 剛才已經(jīng) 出現(xiàn)過一次 num[mid] < num[mid+1]了, 左右夾逼 就成了
3,
如果 num[mid] == num[mid+1]
不可能,因為題目要求了 num[i] ≠ num[i+1]
2, 如果 num[mid] > num[mid+1] 那么說明 peak 在左邊,因為 num[-1] = -∞
同理 查找
*/
// FIXME: 沒有完成
/* MARK: - 復(fù)雜度分析:
時間復(fù)雜度：O(lgn)
*/
// MARK: - 代碼:
private class Solution {
// 利用二分法查找
func findPeakElement(_ nums: [Int]) -> Int {
let n = nums.count
// 一個元素?zé)o需比較,直接retun
if n == 1 {
return 0
} else if n == 0 {
return -1
}
var low = 0
var high = n - 1
var mid1 = 0
var mid2 = 0
while low < high {
mid1 = (high - low)/2 + low
mid2 = mid1 + 1
// 這里mid2 不會越界, 因為n=1的時候直接return掉了
// 并且因為 low<high 所以low≠high, 也就是說 mid1≠high
// 所以mid1始終小于high mid1+1也就不會越界
if nums[mid1] < nums[mid2] {
low = mid2
} else {
high = mid1
}
}
return low
}
// 利用遍歷查找
func findPeakElement2(_ nums: [Int]) -> Int {
let n = nums.count
for i in 1 ..< nums.count {
// 只需要判斷一次就行了, 因為 num[-1] = num[n] = -∞
if nums[i] < nums[i-1] {
return i-1
}
}
return n-1
}
}
// MARK: - 測試代碼:
func findPeakElement() {
print(Solution().findPeakElement([1]))
print(Solution().findPeakElement([1, 2, 5, 1]))
print(Solution().findPeakElement([8, 2, 5, 8]))
}
