Posts tagged as “sort”

花花酱 LeetCode 976. Largest Perimeter Triangle

By zxi on January 14, 2019

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: [2,1,2]
Output: 5

Example 2:

Input: [1,2,1]
Output: 0

Example 3:

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

Example 4:

Input: [3,6,2,3]
Output: 8

Note:

3 <= A.length <= 10000
1 <= A[i] <= 10^6

Solution: Greedy

Answer must be 3 consecutive numbers in the sorted array
if A[i] >= A[i+1] + A[i+2], then A[i] >= A[i+j] + A[i+k], 1 < j < k
if A[i] < A[i+1] + A[i+2], then A[i] + A[i+1] + A[i+2] is the answer

C++

class Solution {

public:

int largestPerimeter(vector<int>& A) {

sort(rbegin(A), rend(A));

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

if (A[i] < A[i + 1] + A[i + 2])

return A[i] + A[i + 1] + A[i + 2];

return 0;

}

};

花花酱 LeetCode 969. Pancake Sorting

By zxi on January 5, 2019

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted.

Example 2:

Input: [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Note:

1 <= A.length <= 100
A[i] is a permutation of [1, 2, ..., A.length]

Solution: Simulation

Put the largest element to its position. Each element requires two flips
e.g. [3, 2, 4, 1]
largest element: 4, index: 2
flip1: [4, 2, 3, 1]
flip2: [1, 3, 2, 4]
Repeat for [1, 3, 2]…

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

vector<int> pancakeSort(vector<int>& A) {

const int n = A.size();

vector<int> ans;

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

int p = max_element(begin(A), end(A) - i) - begin(A);

ans.push_back(p + 1);

std::reverse(begin(A), begin(A) + p + 1);

ans.push_back(n - i);

std::reverse(begin(A), begin(A) + n - i);

}

return ans;

}

};

花花酱 LeetCode 945. Minimum Increment to Make Array Unique

By zxi on November 29, 2018

Problem

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

Example 1:

Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].

Example 2:

Input: [3,2,1,2,1,7]
Output: 6
Explanation:  After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

Note:

0 <= A.length <= 40000
0 <= A[i] < 40000

Solution: Greedy

Sort the elements, make sure A[i] >= A[i-1] + 1, if not increase A[i] to A[i – 1] + 1

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua, 56 ms

class Solution {

public:

int minIncrementForUnique(vector<int>& A) {

int ans = 0;

sort(begin(A), end(A));

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

if (A[i] > A[i - 1]) continue;

ans += (A[i - 1] - A[i]) + 1;

A[i] = A[i - 1] + 1;

}

return ans;

}

};

Python3

# Author: Huahua, Running time: 196 ms

class Solution(object):

def minIncrementForUnique(self, A):

A.sort()

ans = 0

for i in range(1, len(A)):

if A[i] > A[i - 1]: continue

ans += A[i - 1] - A[i] + 1

A[i] = A[i - 1] + 1

return ans

花花酱 LeetCode 937. Reorder Log Files

By zxi on November 10, 2018

Problem

https://leetcode.com/problems/reorder-log-files/description/

You have an array of logs. Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Note:

0 <= logs.length <= 100
3 <= logs[i].length <= 100
logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution: Partition + Sort

partition the array such that all digit logs are after all letter logs
sort the letter logs part based on the log content

Time complexity: O(n + aloga)

Space complexity: O(n)

C++

class Solution {

public:

vector<string> reorderLogFiles(vector<string>& logs) {

auto alpha_end = std::stable_partition(begin(logs), end(logs),

[](const string& log){ return isalpha(log.back()); });

std::sort(begin(logs), alpha_end, [](const string& a, const string& b){

return a.substr(a.find(' ')) < b.substr(b.find(' '));

});

return logs;

}

};

花花酱 LeetCode 922. Sort Array By Parity II

By zxi on October 13, 2018

Problem

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

Solution 1: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArrayByParityII(vector<int>& A) {

vector<int> evens;

vector<int> odds;

for (int a : A)

if (a % 2 == 0)

evens.push_back(a);

else

odds.push_back(a);

auto it1 = begin(evens);

auto it2 = begin(odds);

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

A[i] = *it1++;

swap(it1, it2);

}

return A;

}

};