Posts published in “Array”

花花酱 LeetCode 1093. Statistics from a Large Sample

By zxi on February 6, 2020

We sampled integers between 0 and 255, and stored the results in an array count: count[k] is the number of integers we sampled equal to k.

Return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers. The mode is guaranteed to be unique.

(Recall that the median of a sample is:

The middle element, if the elements of the sample were sorted and the number of elements is odd;
The average of the middle two elements, if the elements of the sample were sorted and the number of elements is even.)

Example 1:

Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,3.00000,2.37500,2.50000,3.00000]

Example 2:

Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,4.00000,2.18182,2.00000,1.00000]

Constraints:

count.length == 256
1 <= sum(count) <= 10^9
The mode of the sample that count represents is unique.
Answers within 10^-5 of the true value will be accepted as correct.

Solution: TreeMap

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

C++

// Author: Huahua

class Solution {

public:

vector<double> sampleStats(vector<int>& count) {

int counts = 0;

int minVal = 255;

int maxVal = 0;

int mode = -1;

int modeCount = 0;

long sum = 0;

map<int, int> m;

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

if (!count[i]) continue;

sum += static_cast<long>(i) * count[i];

minVal = min(minVal, i);

maxVal = max(maxVal, i);

if (count[i] > modeCount) {

mode = i;

modeCount = count[i];

}

m[counts += count[i]] = i;

}

auto it1 = m.lower_bound(counts / 2);

double median = it1->second;

auto it2 = next(it1);

if (counts % 2 == 0 && it2 != m.end() && it1->first == counts / 2) {

median = (median + it2->second) / 2;

}

return {minVal, maxVal, static_cast<double>(sum) / counts, median, mode};

}

};

花花酱 LeetCode 912. Sort an Array

By zxi on February 1, 2020

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

Since n <= 50000, any O(n^2) won’t pass, we need O(nlogn) or better

Solution 1: QuickSort

Time complexity: O(nlogn) ~ O(n^2)
Space complexity: O(logn) ~ O(n)

C++

// Author: Huahua, 60 ms

class Solution {

public:

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

function<void(int, int)> quickSort = [&](int l, int r) {

if (l >= r) return;

int i = l;

int j = r;

int p = nums[l + rand() % (r - l + 1)];

while (i <= j) {

while (nums[i] < p) ++i;

while (nums[j] > p) --j;

if (i <= j)

swap(nums[i++], nums[j--]);

}

quickSort(l, j);

quickSort(i, r);

};

quickSort(0, nums.size() - 1);

return nums;

}

};

Solution 2: Counting Sort

Time complexity: O(n)
Space complexity: O(max(nums) – min(nums))

C++

// Author: Huahua, 54 ms

class Solution {

public:

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

auto [min_it, max_it] = minmax_element(begin(nums), end(nums));

int l = *min_it, r = *max_it;

vector<int> count(r - l + 1);

for (int n : nums) ++count[n - l];

int index = 0;

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

while (count[i]--) nums[index++] = i + l;

return nums;

}

};

Solution 2: HeapSort

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

C++

// Author: Huahua, 72ms

class Solution {

public:

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

priority_queue<int> q(begin(nums), end(nums));

int i = nums.size();

while (!q.empty()) {

nums[--i] = q.top();

q.pop();

}

return nums;

}

};

C++

// Author: Huahua

class Solution {

public:

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

auto heapify = [&](int i, int e) {

while (i <= e) {

int l = 2 * i + 1;

int r = 2 * i + 2;

int j = i;

if (l <= e && nums[l] > nums[j]) j = l;

if (r <= e && nums[r] > nums[j]) j = r;

if (j == i) break;

swap(nums[i], nums[j]);

swap(i, j);

}

};

const int n = nums.size();

// Init heap

for (int i = n / 2; i >= 0; i--)

heapify(i, n - 1);

// Get min.

for (int i = n - 1; i >= 1; i--) {

swap(nums[0], nums[i]);

heapify(0, i - 1);

}

return nums;

}

};

Solution 3: MergeSort

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> t(nums.size());

function<void(int, int)> mergeSort = [&](int l, int r) {

if (l + 1 >= r) return;

int m = l + (r - l) / 2;

mergeSort(l, m);

mergeSort(m, r);

int i1 = l;

int i2 = m;

int index = 0;

while (i1 < m || i2 < r)

if (i2 == r || (i1 < m && nums[i1] < nums[i2]))

t[index++] = nums[i1++];

else

t[index++] = nums[i2++];

std::copy(begin(t), begin(t) + index, begin(nums) + l);

};

mergeSort(0, nums.size());

return nums;

}

};

Solution 4: BST

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

C++

// Author: Huahua

class Solution {

public:

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

multiset<int> s(begin(nums), end(nums));

return {begin(s), end(s)};

}

};

花花酱 LeetCode 1299. Replace Elements with Greatest Element on Right Side

By zxi on December 28, 2019

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Constraints:

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

Solution: Scan from right to left

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

C++

// Author: Huahua

class Solution {

public:

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

int g = -1;

for (int i = arr.size() - 1; i >= 0; --i)

g = max(g, exchange(arr[i], g));

return arr;

}

};

花花酱 LeetCode 1267. Count Servers that Communicate

By zxi on November 23, 2019

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

Solution: Counting

Two passes:
First pass, count number of computers for each row and each column.
Second pass, count grid[i][j] if rows[i] or cols[j] has more than 1 computer.

Time complexity: O(m*n)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

int countServers(vector<vector<int>>& grid) {

const size_t m = grid.size();

const size_t n = grid[0].size();

vector<int> rows(m);

vector<int> cols(n);

for (size_t i = 0; i < m; ++i)

for (size_t j = 0; j < n; ++j) {

rows[i] += grid[i][j];

cols[j] += grid[i][j];

}

int ans = 0;

for (size_t i = 0; i < m; ++i)

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

ans += (rows[i] > 1 || cols[j] > 1) ? grid[i][j] : 0;

return ans;

}

};

花花酱 LeetCode 48. Rotate Image

By zxi on October 2, 2019

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Solution: 2 Passes

First pass: mirror around diagonal
Second pass: mirror around y axis

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

C++

// Author: Huahua

class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

const int n = matrix.size();

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

for (int j = i + 1; j < n; ++j)

swap(matrix[i][j], matrix[j][i]);

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

reverse(begin(matrix[i]), end(matrix[i]));

}

};