Array Archives - Page 31 of 31 - Huahua's Tech Road

Problem:

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:

Input:

letters = ["c", "f", "j"]

target = "a"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "c"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "d"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "g"

Output: "j"

Input:

letters = ["c", "f", "j"]

target = "j"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "k"

Output: "c"

Note:

letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

Link: https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/

Idea:

Scan the array Time complexity: O(n)
Binary search Time complexity: O(logn)

Solution 1:

C++ / Scan

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

for (const char c : letters)

if (c > target) return c;

return letters.front();

}

};

C++ / Set

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

vector<int> seen(26, 0);

for (const char c : letters)

seen[c - 'a'] = 1;

while (true) {

if (++target > 'z') target = 'a';

if (seen[target - 'a']) return target;

}

return ' ';

}

};

C++ / Binary Search

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

int l = 0;

int r = letters.size();

while (l < r) {

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

if (letters[m] <= target)

l = m + 1;

else

r = m;

}

return letters[l % letters.size()];

}

};

https://leetcode.com/problems/maximum-gap/description/

Problem:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

题目大意:

给你一个没有排序的正整数数组。输出排序后，相邻元素的差的最大值(Max Gap)。需要在线性时间内解决。

Example:

Input: [5, 0, 4, 2, 12, 10]

Output: 5

Explanation:

Sorted: [0, 2, 4, 5, 10, 12]

max gap is 10 – 5 = 5

Idea:

Bucket sort. Use n buckets to store all the numbers. For each bucket, only track the min / max value.

桶排序。用n个桶来存放数字。对于每个桶，只跟踪存储最大值和最小值。

max gap must come from two “adjacent” buckets, b[i], b[j], j > i, b[i+1] … b[j – 1] must be empty.

max gap 只可能来自”相邻”的两个桶 b[i] 和 b[j], j > i, b[i] 和 b[j] 之间的桶（如果有）必须为空。

max gap = b[j].min – b[i].min

Time complexity: O(n)

时间复杂度: O(n)

Space complexity: O(n)

空间复杂度: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maximumGap(vector<int>& nums) {

const int n = nums.size();

if (n <= 1) return 0;

const auto mm = minmax_element(nums.begin(), nums.end());

const int range = *mm.second - *mm.first;

const int bin_size = range / n + 1;

vector<int> min_vals(n, INT_MAX);

vector<int> max_vals(n, INT_MIN);

for (const int num : nums) {

const int index = (num - *mm.first) / bin_size;

min_vals[index] = min(min_vals[index], num);

max_vals[index] = max(max_vals[index], num);

}

int max_gap = 0;

int prev_max = max_vals[0];

for (int i = 1; i < n; ++i) {

if (min_vals[i] != INT_MAX) {

max_gap = max(max_gap, min_vals[i] - prev_max);

prev_max = max_vals[i];

}

return max_gap;

}

};

Posts published in “Array”

花花酱 LeetCode 744. Find Smallest Letter Greater Than Target

花花酱 LeetCode 164. Maximum Gap