Posts tagged as “binary search”

花花酱 LeetCode 875. Koko Eating Bananas

By zxi on July 22, 2018

Problem

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

Solution: Binary Search

search for the smallest k [1, max_pile_height] such that eating time h <= H.

Time complexity: O(nlogh)

Space complexity: O(1)

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

int minEatingSpeed(vector<int>& piles, int H) {

int l = 1;

int r = *max_element(begin(piles), end(piles)) + 1;

while (l < r) {

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

int h = 0;

for (int p : piles)

h += (p + m - 1) / m;

if (h <= H)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 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 704. Binary Search

By zxi on July 12, 2018

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:

You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
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)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

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

if (nums[m] == target)

return m;

else if (nums[m] > target)

r = m;

else

l = m + 1;

}

return -1;

}

};

STL

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

auto it = lower_bound(nums.begin(), nums.end(), target);

if (it == nums.end() || *it != target) return -1;

return it - nums.begin();

}

};

花花酱 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;

}

};