Posts published in “Array”

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

}

};

花花酱 LeetCode 495. Teemo Attacking

By zxi on March 8, 2018

题目大意：给你攻击的时间序列以及中毒的时长，求总共的中毒时间。

Problem:

https://leetcode.com/problems/teemo-attacking/description/

In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately. 
This poisoned status will last 2 seconds until the end of time point 2. 
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds. 
So you finally need to output 4.

Example 2:

Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned. 
This poisoned status will last 2 seconds until the end of time point 2. 
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status. 
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3. 
So you finally need to output 3.

Note:

You may assume the length of given time series array won’t exceed 10000.
You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

Idea: Running Process

Compare the current attack time with the last one, if span is more than duration, add duration to total, otherwise add (curr – last).

C++

// Author: Huahua

// Running time: 66 ms

class Solution {

public:

int findPoisonedDuration(vector<int>& t, int duration) {

if (t.empty()) return 0;

int total = 0;

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

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

};

Java

// Author: Huahua

// Running time: 9 ms

class Solution {

public int findPoisonedDuration(int[] t, int duration) {

if (t.length == 0) return 0;

int total = 0;

for (int i = 1; i < t.length; ++ i)

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

Python3

"""

Author: Huahua

Running time: 64 ms (beats 100%)

"""

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

l = timeSeries[0]

total = 0

for t in timeSeries:

total += duration if t - l > duration else t - l

l = t

return total + duration

import numpy as np

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

d = np.diff(timeSeries)

d = np.clip(d, 0, duration)

return int(np.sum(d) + duration)

class Solution:

def findPoisonedDuration(self, t, duration):

return sum([min(c - l, duration) for l, c in zip(t, t[1:] + [1e9])])

花花酱 LeetCode 496. Next Greater Element I

By zxi on March 5, 2018

题目大意：给你一个组数A里面每个元素都不相同。再给你一个数组B，元素是A的子集，问对于B中的每个元素，在A数组中相同元素之后第一个比它的元素是多少。

Problem:

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1‘s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].

Output: [-1,3,-1]

Explanation:

For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.

For number 1 in the first array, the next greater number for it in the second array is 3.

For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].

Output: [3,-1]

Explanation:

For number 2 in the first array, the next greater number for it in the second array is 3.

For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

vector<int> ans;

for (int num : findNums) {

ans.push_back(-1);

int index = std::find(nums.begin(), nums.end(), num) - nums.begin();

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

if (nums[i] > num) {

ans.back() = nums[i];

break;

}

return ans;

}

};

Solution 2: HashTable + Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

unordered_map<int, int> indices;

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

indices[nums[i]] = i;

vector<int> ans;

for (int num : findNums) {

ans.push_back(-1);

for (int i = indices[num]; i < nums.size(); ++i)

if (nums[i] > num) {

ans.back() = nums[i];

break;

}

return ans;

}

};

Solution 3: Stack + HashTable

Using a stack to store the nums whose next greater isn’t found yet.

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

stack<int> s;

unordered_map<int, int> next;

for (int num : nums) {

while (!s.empty() && num > s.top()) {

next[s.top()] = num;

s.pop();

}

s.push(num);

}

vector<int> ans;

for (int num : findNums)

ans.push_back(next.count(num) ? next[num] : -1);

return ans;

}

};

花花酱 LeetCode 795. Number of Subarrays with Bounded Maximum

By zxi on March 3, 2018

题目大意：问一个数组中有多少个子数组的最大元素值在[L, R]的范围里。

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :

Input:

A = [2, 1, 4, 3]

L = 2

R = 3

Output: 3

Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Solution 1:

C++

// Author: Huahua

// Running time: 42 ms

class Solution {

public:

int numSubarrayBoundedMax(vector<int>& A, int L, int R) {

return count(A, R) - count(A, L - 1);

}

private:

// Count # of sub arrays whose max element is <= N

int count(const vector<int>& A, int N) {

int ans = 0;

int cur = 0;

for (int a: A) {

if (a <= N)

ans += ++cur;

else

cur = 0;

}

return ans;

}

};

Solution 2: One pass

C++

// Author: Huahua

// Running time: 38 ms

class Solution {

public:

int numSubarrayBoundedMax(vector<int>& A, int L, int R) {

int ans = 0;

int left = -1;

int right = -1;

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

if (A[i] >= L) right = i;

if (A[i] > R) left = i;

ans += (right - left);

}

return ans;

}

};

花花酱 LeetCode 786. K-th Smallest Prime Fraction

By zxi on February 20, 2018

题目大意：给你一些互质数字，求出它们组成的分数中第K小的分数。

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:

Input: A = [1, 2, 3, 5], K = 3

Output: [2, 5]

Explanation:

The fractions to be considered in sorted order are:

1/5, 1/3, 2/5, 1/2, 3/5, 2/3.

The third fraction is 2/5.

Input: A = [1, 7], K = 1

Output: [1, 7]

Note:

A will have length between 2 and 2000.
Each A[i] will be between 1 and 30000.
K will be between 1 and A.length * (A.length + 1) / 2.

Solution 1: Binary Search

Binary search m, 0 < m < 1, such that there are exact k pairs of (i, j) that A[i] / A[j] < m

Time complexity: O(n*C) C <= 31

C++

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {

const int n = A.size();

double l = 0;

double r = 1.0;

while (l < r) {

double m = (l + r) / 2;

double max_f = 0.0;

int total = 0;

int p, q = 0;

for (int i = 0, j = 1; i < n - 1; ++i) {

while (j < n && A[i] > m * A[j]) ++j;

if (n == j) break;

total += (n - j);

const double f = static_cast<double>(A[i]) / A[j];

if (f > max_f) {

p = i;

q = j;

max_f = f;

}

if (total == K)

return {A[p], A[q]};

else if (total > K)

r = m;

else

l = m;

}

return {};

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int[] kthSmallestPrimeFraction(int[] A, int K) {

final int n = A.length;

double l = 0;

double r = 1.0;

while (l < r) {

double m = (l + r) / 2;

double max_f = 0.0;

int total = 0;

int p = 0;

int q = 0;

for (int i = 0, j = 1; i < n - 1; ++i) {

while (j < n && A[i] > m * A[j]) ++j;

if (n == j) break;

total += (n - j);

final double f = (double)A[i] / A[j];

if (f > max_f) {

p = i;

q = j;

max_f = f;

}

if (total == K)

return new int[]{A[p], A[q]};

else if (total > K)

r = m;

else

l = m;

}

return new int[] {};

}

Python3

"""

Author: Huahua

Running time: 172 ms

"""

class Solution:

def kthSmallestPrimeFraction(self, A, K):

n = len(A)

l = 0.0

r = 1.0

while l < r:

m = (l + r) / 2

max_f = 0.0

total = 0

j = 1

for i in range(n - 1):

while j < n and A[i] > m * A[j]: j += 1

if j == n: break

total += n - j

f = A[i] / A[j]

if f > max_f:

p, q, max_f = i, j, f

if total == K:

return [A[p], A[q]]

elif total > K:

r = m

else:

l = m

return []

Related Problems: