Leetcode-Question-719: Find K-th Smallest Pair Distance

原文链接:
https://leetcode.com/contest/leetcode-weekly-contest-56/problems/find-k-th-smallest-pair-distance/

解析:

Binary Search

 

Leetcode-Question-154: Find Minimum in Rotated Sorted Array II

原文链接:
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

题目描述:
154. Find Minimum in Rotated Sorted Array II
Difficulty: Hard

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

解析:二分查找,但考虑到有重复,在最坏情况下的时间复杂度为O(n)。

 

Leetcode-Question-35: Search Insert Position

原文链接:
https://leetcode.com/problems/search-insert-position/

题目描述:
35. Search Insert Position
Difficulty: Medium

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

解析:

 

Leetcode-Question-278: First Bad Version

原文链接:
https://leetcode.com/problems/first-bad-version/

题目描述:

First Bad Version
Difficulty: Easy

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

解析:

注意mid 不要直接写成(low+high)/2,因为它会溢出。同时考虑到了无版本坏的情况。