Posts tagged as “sort”

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

}

};

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

}

};