Posts tagged as “sorting”

花花酱 LeetCode 791. Custom Sort String

By zxi on February 24, 2018

题目大意：给你字符的顺序，让你排序一个字符串。

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :

Input:

S = "cba"

T = "abcd"

Output: "cbad"

Explanation:

"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

Store the order of char in a hashtable
Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

string customSortString(string S, string T) {

vector<int> order(128, INT_MAX);

int i = 0;

for (char c: S)

if (order[c] == INT_MAX) order[c] = ++i;

std::sort(T.begin(), T.end(), [&order](const char c1, const char c2){

return order[c1] < order[c2];

});

return T;

}

};

花花酱 LeetCode 769. Max Chunks To Make Sorted

By zxi on February 2, 2018

题目大意：给你一个0 ~ n-1的排列，问你最多能分成几组，每组分别排序后能够组成0 ~ n-1。

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [4,3,2,1,0]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]

Output: 4

Explanation:

We can split into two chunks, such as [1, 0], [2, 3, 4].

However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Note:

arr will have length in range [1, 10].
arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

set<int> s;

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

s.insert(arr[i]);

if (*s.rbegin() == i) ++ans;

}

return ans;

}

};

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

int m = 0;

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

m = max(m, arr[i]);

if (m == i) ++ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 5 ms

class Solution {

public int maxChunksToSorted(int[] arr) {

int max = 0;

int ans = 0;

for (int i = 0; i < arr.length; ++i) {

max = Math.max(max, arr[i]);

if (max == i) ++ans;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 53 ms

"""

class Solution:

def maxChunksToSorted(self, arr):

m = 0

ans = 0

for i, n in enumerate(arr):

if n > m: m = n

if m == i: ans += 1

return ans

花花酱 LeetCode 480. Sliding Window Median

By zxi on January 28, 2018

题目大意：让你求移动窗口的中位数。

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Median

--------------- -----

[1 3 -1] -3 5 3 6 7 1

1 [3 -1 -3] 5 3 6 7 -1

1 3 [-1 -3 5] 3 6 7 -1

1 3 -1 [-3 5 3] 6 7 3

1 3 -1 -3 [5 3 6] 7 5

1 3 -1 -3 5 [3 6 7] 6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.

Solution 0: Brute Force

Time complexity: O(n*klogk) TLE 32/42 test cases passed

Solution 1: Insertion Sort

Time complexity: O(k*logk + (n – k + 1)*k)

Space complexity: O(k)

C++ / vector

// Author: Huahua

// Running time: 99 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

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

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::find(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

C++ / vector + binary_search for deletion.

// Author: Huahua

// Running time: 84 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

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

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::lower_bound(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 60 ms

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

for (int i = 0; i < k; ++i)

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = 0;

while (i < window.length - 1 && val > window[i]) ++i;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = 0;

while (i < window.length && val != window[i]) ++i;

while (i < window.length - 1) window[i] = window[++i];

}

Java / Binary Search

// Author: Huahua

// Running time: 47 ms (<98.96%)

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

for (int i = 0; i < k; ++i)

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

if (i < 0) i = - i - 1;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

while (i < window.length - 1) window[i] = window[++i];

}

Python

"""

Author: Huahua

Running time: 161 ms (< 93.75%)

"""

class Solution:

def medianSlidingWindow(self, nums, k):

if k == 0: return []

ans = []

window = sorted(nums[0:k])

for i in range(k, len(nums) + 1):

ans.append((window[k // 2] + window[(k - 1) // 2]) / 2.0)

if i == len(nums): break

index = bisect.bisect_left(window, nums[i - k])

window.pop(index)

bisect.insort_left(window, nums[i])

return ans

Solution 2: BST

// Author: Huahua

// Running time: 68 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

multiset<int> window(nums.begin(), nums.begin() + k);

auto mid = next(window.begin(), (k - 1) / 2);

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

ans.push_back((static_cast<double>(*mid) +

*next(mid, (k + 1) % 2)) / 2.0);

if (i == nums.size()) break;

window.insert(nums[i]);

if (nums[i] < *mid) --mid;

if (nums[i - k] <= *mid) ++mid;

window.erase(window.lower_bound(nums[i - k]));

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 759. Employee Free Time

By zxi on January 8, 2018

题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。

Problem:

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]

Output: [[3,4]]

Explanation:

There are a total of three employees, and all common

free time intervals would be [-inf, 1], [3, 4], [10, inf].

We discard any intervals that contain inf as they aren't finite.

Example 2:

1 2	Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

schedule and schedule[i] are lists with lengths in range [1, 50].
0 <= schedule[i].start < schedule[i].end <= 10^8.

Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

// Author: Huahua

// Running time: 81 ms

class Solution {

public:

vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {

vector<Interval> all;

for (const auto intervals : schedule)

all.insert(all.end(), intervals.begin(), intervals.end());

std::sort(all.begin(), all.end(),

[](const Interval& a, const Interval& b){

return a.start < b.start;

});

vector<Interval> ans;

int end = all.front().end;

for (const Interval& busy : all) {

if (busy.start > end)

ans.emplace_back(end, busy.start);

end = max(end, busy.end);

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 164. Maximum Gap

By zxi on December 10, 2017

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;

}

};