Posts published in “Binary Search”

花花酱 LeetCode 287. Find the Duplicate Number

By zxi on July 14, 2018

Problem

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n²).
There is only one duplicate number in the array, but it could be repeated more than once.

Solution1: Binary Search

Time complexity: O(nlogn)

Space complexity: O(1)

Find the smallest m such that len(nums <= m) > m, which means m is the duplicate number.

In the sorted form [1, 2, …, m1, m2, m + 1, …, n]

There are m+1 numbers <= m

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int findDuplicate(vector<int>& nums) {

int l = 1;

int r = nums.size();

while (l < r) {

int m = (r - l) / 2 + l;

int count = 0; // len(nums <= m)

for (int num : nums)

if (num <= m) ++count;

if (count <= m)

l = m + 1;

else

r = m;

}

return l;

}

};

Solution: Linked list cycle

Convert the problem to find the entry point of the cycle in a linked list.

Take the number in the array as the index of next node.

[1,3,4,2,2]

0->1->3->2->4->2 cycle: 2->4->2

[3,1,3,4,2]

0->3->4->2->3->4->2 cycle 3->4->2->3

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int findDuplicate(vector<int>& nums) {

int slow = 0;

int fast = 0;

while (true) {

slow = nums[slow];

fast = nums[nums[fast]];

if (slow == fast) break;

}

fast = 0;

while (fast != slow) {

slow = nums[slow];

fast = nums[fast];

}

return slow;

}

};

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

By zxi on June 17, 2018

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:

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

Solution1: Liner Scan

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

for (int i = 1; i < A.size(); ++i)

if (A[i] < A[i - 1]) return i - 1;

}

};

C++/STL

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

return max_element(begin(A), end(A)) - begin(A);

}

};

Solution 2: Binary Search

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

Time complexity: O(logn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

int l = 0;

int r = A.size();

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

};

Java

// Author: Huahua, 3 ms

class Solution {

public int peakIndexInMountainArray(int[] A) {

int l = 0;

int r = A.length;

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

Python3

# Author: Huahua, 40 ms

class Solution:

def peakIndexInMountainArray(self, A):

l, r = 0, len(A)

while l < r:

m = l + (r - l) // 2

if A[m] > A[m + 1]:

r = m

else:

l = m + 1

return l

花花酱 LeetCode 275. H-Index II

By zxi on March 15, 2018

题目大意：给你已排序的引用次数的数组，求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++

// Author: Huahua

// Running time: 33 ms

class Solution {

public:

int hIndex(vector<int>& citations) {

for (int i = 1; i <= citations.size(); ++i)

if (*(citations.rbegin() + i - 1) < i) return i - 1;

return citations.size();

}

};

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int hIndex(vector<int>& citations) {

int n = citations.size();

int l = 0;

int r = n;

while (l < r) {

int m = l + (r - l) / 2;

if (citations[n - m - 1] <= m)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 278. First Bad Version

By zxi on March 15, 2018

题目大意：给你一个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)

// Forward declaration of isBadVersion API.

bool isBadVersion(int version);

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

int firstBadVersion(int n) {

int l = 1;

int r = n;

while (l < r) {

int m = l + (r - l) / 2;

if (isBadVersion(m))

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 506. Relative Ranks

By zxi on March 8, 2018

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

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:

Input: [5, 4, 3, 2, 1]

Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal".

For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

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

Solution 1: Sorting ( + Binary Search)

C++

class Solution {

public:

vector<string> findRelativeRanks(vector<int>& nums) {

vector<string> ans;

vector<int> s(nums);

std::sort(s.begin(), s.end());

vector<string> medals{"Gold", "Silver", "Bronze"};

for (int i = 0; i < nums.size(); ++i) {

int rank = s.end() - std::lower_bound(s.begin(), s.end(), nums[i]);

if (rank <= 3)

ans.push_back(medals[rank - 1] + " Medal");

else

ans.push_back(std::to_string(rank));

}

return ans;

}

};

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<string> findRelativeRanks(vector<int>& nums) {

vector<pair<int, int>> s;

for (int i = 0; i < nums.size(); ++i)

s.emplace_back(nums[i], i);

vector<string> medals{"Gold", "Silver", "Bronze"};

std::sort(s.rbegin(), s.rend());

vector<string> ans(nums.size());

for (int i = 0; i < s.size(); ++i)

ans[s[i].second] = i < 3 ? (medals[i] + " Medal") : std::to_string(i + 1);

return ans;

}

};