Posts tagged as “sort”

花花酱 LeetCode 1365. How Many Numbers Are Smaller Than the Current Number

By zxi on March 2, 2020

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints:

2 <= nums.length <= 500
0 <= nums[i] <= 100

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {

const int n = nums.size();

vector<int> ans(n);

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

for (int j = 0; j < n; ++j)

if (i != j && nums[j] < nums[i]) ++ans[i];

return ans;

}

};

Solution 2: Sort + Binary Search

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {

const int n = nums.size();

vector<int> s(nums);

sort(begin(s), end(s));

vector<int> ans(n);

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

ans[i] = distance(begin(s), lower_bound(begin(s), end(s), nums[i]));

return ans;

}

};

Solution 3: Cumulative frequency

Time complexity: O(n)
Space complexity: O(101)

C++

// Author: Huahua

class Solution {

public:

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {

vector<int> f(101);

for (int x : nums) ++f[x];

partial_sum(begin(f), end(f), begin(f));

for (int& x : nums)

x = x == 0 ? 0 : f[x - 1];

return nums;

}

};

花花酱 LeetCode 1356. Sort Integers by The Number of 1 Bits

By zxi on February 22, 2020

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Example 3:

Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:

Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:

Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 10^4

Solution: Sorting

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortByBits(vector<int>& arr) {

sort(begin(arr), end(arr), [](const int a, const int b){

int key_a = __builtin_popcount(a);

int key_b = __builtin_popcount(b);

if (key_a != key_b) return key_a < key_b;

return a < b;

});

return arr;

}

};

Python3

# Author: Huahua

class Solution:

def sortByBits(self, arr: List[int]) -> List[int]:

return sorted(arr, key=lambda x: (bin(x).count('1') << 16) + x)

花花酱 LeetCode 853. Car Fleet

By zxi on April 28, 2019

N cars are going to the same destination along a one lane road. The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored – they are assumed to have the same position.

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
All initial positions are different.

Solution: Greedy

Compute the time when each car can reach target.
Sort cars by position DESC

Answer will be number slow cars in the time array.

Ex 1: 
target = 12
p = [10,8,0,5,3] 
v = [2,4,1,1,3]


p     t
10    1  <- slow -- ^
 8    1             |
 5    7  <- slow -- ^
 3    3             |
 0   12  <- slow -- ^

Ex 2
target = 10
p = [5, 4, 3, 2, 1]
v = [1, 2, 3, 4, 5]

p     t
5     5  <- slow -- ^
4     3             |
3     2.33          |
2     2             |
1     1.8           |

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, running time: 52 ms / 10.9 MB

class Solution {

public:

int carFleet(int target, vector<int>& position, vector<int>& speed) {

vector<pair<int, float>> cars(position.size());

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

cars[i] = {position[i], static_cast<float>(target - position[i]) / speed[i]};

sort(rbegin(cars), rend(cars));

int ans{0};

float max_t{0};

for (const auto& [p, t] : cars)

if (t > max_t) {

max_t = t;

++ans;

}

return ans;

}

};

Python3

class Solution:

def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:

cars = sorted([(p, (target - p) / s) for p, s in zip(position, speed)],

key=lambda x: -x[0])

ans, max_t = 0, 0

for p, t in cars:

if t > max_t:

ans += 1

max_t = t

return ans

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

}

};