Posts tagged as “sort”

花花酱 LeetCode 26. Remove Duplicates from Sorted Array

By zxi on October 2, 2018

Problem

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

const int n = nums.size();

if (n <= 1) return n;

int ans = 0;

int i = 0;

while (i < n) {

nums[ans++] = nums[i];

int j = i + 1;

while (j < n && nums[j] == nums[j - 1]) ++j;

i = j;

}

return ans;

}

};

花花酱 LeetCode 88. Merge Sorted Array

By zxi on September 27, 2018

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

Solution:

Fill nums1 from back to front

Time complexity: O(m + n)

Space complexity: O(1) in-place

C++

// Author: Huahua

class Solution {

public:

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

int i = m - 1;

int j = n - 1;

int tail = m + n - 1;

while (j >= 0)

nums1[tail--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];

}

};

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

}

};