Posts tagged as “sort”

花花酱 LeetCode 905. Sort Array By Parity

By zxi on September 15, 2018

Problem

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]

Output: [2,4,3,1]

The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

Solution 1: Split Odd/Even

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

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

vector<int> even;

vector<int> odd;

for (int a : A) {

if (a % 2) odd.push_back(a);

else even.push_back(a);

}

even.insert(end(even), begin(odd), end(odd));

return even;

}

};

Solution 2: Stable sort by key % 2

Time complexity: O(nlogn)

Space complexity: O(1) in-place

C++

// Author: Huahua, 52 ms

class Solution {

public:

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

stable_sort(begin(A), end(A), [](int a, int b){

return a % 2 < b % 2;

});

return A;

}

};

花花酱 LeetCode 899. Orderly Queue

By zxi on September 1, 2018

Problem

A string S of lowercase letters is given. Then, we may make any number of moves.

In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.

Return the lexicographically smallest string we could have after any number of moves.

Example 1:

Input: S = "cba", K = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".

Example 2:

Input: S = "baaca", K = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".

Note:

1 <= K <= S.length <= 1000
S consists of lowercase letters only.

Solution: Rotation or Sort?

if \(k =1\), we can only rotate the string.

if \(k > 1\), we can bubble sort the string.

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string orderlyQueue(string S, int K) {

if (K > 1) {

sort(begin(S), end(S));

return S;

}

string ans = S;

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

ans = min(ans, S.substr(i) + S.substr(0, i));

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String orderlyQueue(String S, int K) {

if (K > 1) {

char[] chars = S.toCharArray();

Arrays.sort(chars);

return new String(chars);

}

String ans = S;

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

String tmp = S.substring(i) + S.substring(0, i);

if (tmp.compareTo(ans) < 0) ans = tmp;

}

return ans;

}

Python3 SC O(n^2)

# Author: Huahua 48 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

return min([S[i:] + S[0:i] for i in range(0, len(S))])

Python3 SC O(n)

# Author: Huahua 36 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

ans = S

for i in range(0, len(S)):

ans = min(ans, S[i:] + S[0:i])

return ans

花花酱 LeetCode 891. Sum of Subsequence Widths

By zxi on August 20, 2018

Problem

Given an array of integers A, consider all non-empty subsequences of A.

For any sequence S, let the width of S be the difference between the maximum and minimum element of S.

Return the sum of the widths of all subsequences of A.

As the answer may be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: [2,1,3]
Output: 6
Explanation:
Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.

Note:

1 <= A.length <= 20000
1 <= A[i] <= 20000

Solution: Math

Sort the array, for A[i]:

i numbers <= A[i]. A[i] is the upper bound of 2^i subsequences.
n – i – 1 numbers >= A[i]. A[i] is the lower bound of 2^(n – i – 1) subsequences.
A[i] contributes A[i] * 2^i – A[i] * 2^(n – i – 1) to the ans.

\(ans = \sum\limits_{i=0}^{n-1}A_{i}2^{i} – A_{i}2^{n – i – 1} =\sum\limits_{i=0}^{n-1}(A_i – A_{n-i-1})2^{i}\)

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 56 ms

class Solution {

public:

int sumSubseqWidths(vector<int>& A) {

constexpr long kMod = 1e9 + 7;

const int n = A.size();

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

long ans = 0;

long p = 1;

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

ans = (ans + (A[i] - A[n - i - 1]) * p) % kMod;

p = (p << 1) % kMod;

}

return (ans + kMod) % kMod;

}

};

Time complexity: O(n)

Space complexity: O(n)

Counting sort

// Author: Huahua

// Running time: 16 / 44 ms (beats 100%)

static auto x = [](){std::ios::sync_with_stdio(false);cin.tie(nullptr);return nullptr;}();

class Solution {

public:

int sumSubseqWidths(vector<int>& A) {

constexpr long kMod = 1e9 + 7;

const int n = A.size();

countingSort(A);

long ans = 0;

long p = 1;

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

ans = (ans + (A[i] - A[n - i - 1]) * p) % kMod;

p = (p << 1) % kMod;

}

return (ans + kMod) % kMod;

}

private:

void countingSort(vector<int>& A) {

int max_v = INT_MIN;

int min_v = INT_MAX;

for (int a : A) {

if (a > max_v) max_v = a;

if (a < min_v) min_v = a;

}

vector<int> c(max_v - min_v + 1);

for (int a : A)

++c[a - min_v];

int i = 0;

int j = 0;

while (i < c.size()) {

if (--c[i] >= 0)

A[j++] = i + min_v;

else

++i;

}

};

花花酱 LeetCode 628. Maximum Product of Three Numbers

By zxi on August 17, 2018

Problem

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

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

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

The length of the given array will be in range [3,10⁴] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

Idea:

Find the top 3 numbers t1, t2, t3, and bottom 2 numbers, b1, b2.

If all numbers are positives, answer must be t1 * t2 * t3.

Since the number can go negative, the answer must be either t1*t2*t3 or b1 * b2 * t1, if b1 and b2 are both negatives.

ex. nums: [5, 1, -6, 3, -1]

t1, t2, t3: 5, 3, 1

b1, b2: -6, -1

t1 * t2 * t3 = 15

t1 * b1 * b2 = 30

Solution 1: Manual Tracking

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int maximumProduct(vector<int>& nums) {

int max1 = INT_MIN;

int max2 = INT_MIN;

int max3 = INT_MIN;

int min1 = INT_MAX;

int min2 = INT_MAX;

for (const int num: nums) {

if (num > max1) {

max3 = max2;

max2 = max1;

max1 = num;

} else if (num > max2) {

max3 = max2;

max2 = num;

} else if (num > max3) {

max3=num;

}

if (num < min1) {

min2 = min1;

min1 = num;

} else if (num < min2) {

min2=num;

}

return max(max1*max2*max3, max1*min1*min2);

}

};

Solution 2: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

int maximumProduct(vector<int>& nums) {

int n = nums.size();

sort(nums.rbegin(), nums.rend());

return max(nums[0] * nums[1] * nums[2], nums[0] * nums[n - 1] * nums[n - 2]);

}

};

Solution 3: Two Heaps (Priority Queues)

Time complexity: O(nlog3)

Space complexity: O(2 + 3)

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int maximumProduct(vector<int>& nums) {

priority_queue<int, vector<int>, less<int>> min_q; // max_heap

priority_queue<int, vector<int>, greater<int>> max_q; // min_heap

for (int num : nums) {

max_q.push(num);

if (max_q.size() > 3) max_q.pop();

min_q.push(num);

if (min_q.size() > 2) min_q.pop();

}

int max3 = max_q.top(); max_q.pop();

int max2 = max_q.top(); max_q.pop();

int max1 = max_q.top(); max_q.pop();

int min2 = min_q.top(); min_q.pop();

int min1 = min_q.top(); min_q.pop();

return max(max1 * max2 * max3, max1 * min1 * min2);

}

};

花花酱 LeetCode 148. Sort List

By zxi on July 26, 2018

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution: Merge Sort

Top-down (recursion)

Time complexity: O(nlogn)

Space complexity: O(logn)

C++

// Author: Huahua

// Running time: 32 ms

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next) {

fast = fast->next->next;

slow = slow->next;

}

ListNode* mid = slow->next;

slow->next = nullptr; // Break the list.

return merge(sortList(head), sortList(mid));

}

private:

ListNode* merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

return dummy.next;

}

};

Java

// Author: Huahua

// Running time: 6 ms

class Solution {

public ListNode sortList(ListNode head) {

if (head == null || head.next == null) return head;

ListNode slow = head;

ListNode fast = head.next;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

}

ListNode mid = slow.next;

slow.next = null;

return merge(sortList(head), sortList(mid));

}

private ListNode merge(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null && l2 != null) {

if (l1.val > l2.val) {

ListNode tmp = l1;

l1 = l2;

l2 = tmp;

}

tail.next = l1;

l1 = l1.next;

tail = tail.next;

}

tail.next = (l1 != null) ? l1 : l2;

return dummy.next;

}

Python3

# Author: Huahua, 232 ms

class Solution:

def sortList(self, head):

def merge(l1, l2):

dummy = ListNode(0)

tail = dummy

while l1 and l2:

if l1.val > l2.val: l1, l2 = l2, l1

tail.next = l1

l1 = l1.next

tail = tail.next

tail.next = l1 if l1 else l2

return dummy.next

if not head or not head.next: return head

slow = head

fast = head.next

while fast and fast.next:

fast = fast.next.next

slow = slow.next

mid = slow.next

slow.next = None

return merge(self.sortList(head), self.sortList(mid))

bottom up

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

int len = 1;

ListNode* cur = head;

while (cur = cur->next) ++len;

ListNode dummy(0);

dummy.next = head;

ListNode* l;

ListNode* r;

ListNode* tail;

for (int n = 1; n < len; n <<= 1) {

cur = dummy.next; // partial sorted head

tail = &dummy;

while (cur) {

l = cur;

r = split(l, n);

cur = split(r, n);

auto merged = merge(l, r);

tail->next = merged.first;

tail = merged.second;

}

return dummy.next;

}

private:

// Splits the list into two parts, first n element and the rest.

// Returns the head of the rest.

ListNode* split(ListNode* head, int n) {

while (--n && head)

head = head->next;

ListNode* rest = head ? head->next : nullptr;

if (head) head->next = nullptr;

return rest;

}

// Merges two lists, returns the head and tail of the merged list.

pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

while (tail->next) tail = tail->next;

return {dummy.next, tail};

}

};