Press "Enter" to skip to content

Posts tagged as “binary search”

花花酱 LeetCode 704. Binary Search

Problem

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

 

Note:

  1. You may assume that all elements in nums are unique.
  2. n will be in the range [1, 10000].
  3. The value of each element in nums will be in the range [-9999, 9999].

Solution: Binary Search

Time complexity: O(logn)

Space complexity: O(1)

STL

 

花花酱 LeetCode 852. Peak Index in a Mountain Array

Problem

Let’s call an array A a mountain if the following properties hold:

  • A.length >= 3
  • There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

Input: [0,2,1,0]
Output: 1

Note:

  1. 3 <= A.length <= 10000
  2. 0 <= A[i] <= 10^6
  3. A is a mountain, as defined above.

Solution1: Liner Scan

Time complexity: O(n)

Space complexity: O(1)

C++

C++/STL

Solution 2: Binary Search

Find the smallest l such that A[l] > A[l + 1].

Time complexity: O(logn)

Space complexity: O(1)

C++

Java

Python3

花花酱 LeetCode 275. H-Index II

题目大意:给你已排序的引用次数的数组,求h-index。

Problem:

https://leetcode.com/problems/h-index-ii/description/

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Solution 1: Linear Scan

Time complexity: O(n)

Space complexity: O(1)

C++

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

 

花花酱 LeetCode 278. First Bad Version

题目大意:给你一个API查询版本是否坏了,让你找出第一个坏掉的版本。

Problem:

https://leetcode.com/problems/first-bad-version/description/

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.

Solution 1: Brute Force

Time Complexity: O(n) TLE

Space Complexity: O(1)

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

 

花花酱 LeetCode 506. Relative Ranks

题目大意:给你一些人的分数,让你输出他们的排名,前三名输出金银铜牌。

Problem: 

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

Note:

  1. N is a positive integer and won’t exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

Solution 1: Sorting ( + Binary Search)

C++