花花酱 LeetCode 396. Rotate Function

By zxi on March 16, 2018

Problem:

Given an array of integers A and let n to be its length.

Assume B_k to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * B_k[0] + 1 * B_k[1] + ... + (n-1) * B_k[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 10⁵.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution 1: Brute Force

Time complexity: O(n^2) TLE

Space complexity: O(1)

Solution 2: Math

F(K)          =               0A[K] + 1A[K+1] + 2A[K+2] + ... + (n-2)A[K-2] + (n-1)A[K-1]
F(K-1)        =     0A[K-1] + 1A[K] + 2A[K+1] + 3A[K+2] + ... + (n-1)A[K-2]
F(K) - F(K-1) = (n-1)A[K-1] - 1A[K] - 1A[K+1] - 1A[K+2] - ... -     1A[K-2]
              = (n-1)A[K-1] - (1A[K] + 1A[K+1] + ... + 1A[K-2] + 1A[K-1] - 1A[K-1])
              = nA[K-1] - sum(A)
compute F(0)
F(i)          = F(i-1) + nA[i-1] - sum(A)

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

const int n = A.size();

int sum = 0;

int f = 0;

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

sum += A[i];

f += i * A[i];

}

int ans = f;

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

f = f + sum - n * A[n - i - 1];

ans = max(ans, f);

}

return ans;

}

};

花花酱 LeetCode 398. Random Pick Index

By zxi on March 16, 2018

Problem:

https://leetcode.com/problems/random-pick-index/description/

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};

Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.

solution.pick(1);

Solution: Reservoir sampling

https://en.wikipedia.org/wiki/Reservoir_sampling

Time complexity: O(query * n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 92 ms

class Solution {

public:

Solution(vector<int> nums) {

nums_ = std::move(nums);

}

int pick(int target) {

int n = 0;

int index = -1;

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

if (nums_[i] != target) continue;

++n;

if (rand() % n == 0) index = i;

}

return index;

}

private:

vector<int> nums_;

};

花花酱 LeetCode 384. Shuffle an Array

By zxi on March 16, 2018

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.

int[] nums = {1,2,3};

Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.

solution.shuffle();

// Resets the array back to its original configuration [1,2,3].

solution.reset();

// Returns the random shuffling of array [1,2,3].

solution.shuffle();

C++

// Author: Huahua

// Running time: 249 ms

class Solution {

public:

Solution(vector<int> nums) {

nums_ = std::move(nums);

}

/** Resets the array to its original configuration and return it. */

vector<int> reset() {

return nums_;

}

/** Returns a random shuffling of the array. */

vector<int> shuffle() {

vector<int> output(nums_);

const int n = nums_.size();

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

int j = rand() % (n - i) + i;

std::swap(output[i], output[j]);

}

return output;

}

private:

vector<int> nums_;

};

花花酱 LeetCode 697. Degree of an Array

By zxi on March 8, 2018

题目大意：求”度”相同的最短子数组的长度。

Problem:

https://leetcode.com/problems/degree-of-an-array/description/

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

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

Output: 2

Explanation:

The input array has a degree of 2 because both elements 1 and 2 appear twice.

Of the subarrays that have the same degree:

[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]

The shortest length is 2. So return 2.

Example 2:

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

Solution 1: Hashtable

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 33 ms (beats 90.96%)

class Solution {

public:

int findShortestSubArray(vector<int>& nums) {

unordered_map<int, vector<int>> indices;

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

indices[nums[i]].push_back(i);

size_t degree = 0;

for (const auto& p : indices)

degree = max(degree, p.second.size());

int ans = nums.size();

for (const auto& p : indices) {

if (p.second.size() != degree) continue;

ans = min(ans, p.second.back() - p.second.front() + 1);

}

return ans;

}

};

花花酱 LeetCode 349. Intersection of Two Arrays

By zxi on March 8, 2018

题目大意：求2个数组的交集。

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

Each element in the result must be unique.
The result can be in any order.

C++ using std::set_intersection

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

vector<int> intersection(max(nums1.size(), nums2.size()));

std::sort(nums1.begin(), nums1.end());

std::sort(nums2.begin(), nums2.end());

// Inputs must be in ascending order

auto it = std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), intersection.begin());

intersection.resize(it - intersection.begin());

std::set<int> s(intersection.begin(), intersection.end());

return vector<int>(s.begin(), s.end());

}

};

C++ hashtable

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

unordered_set<int> m(nums1.begin(), nums1.end());

vector<int> ans;

for (int num : nums2) {

if (!m.count(num)) continue;

ans.push_back(num);

m.erase(num);

}

return ans;

}

};

Posts published in “Array”

花花酱 LeetCode 396. Rotate Function

Problem:

Solution 1: Brute Force

Solution 2: Math

花花酱 LeetCode 398. Random Pick Index

Problem:

Example:

Solution: Reservoir sampling

花花酱 LeetCode 384. Shuffle an Array

花花酱 LeetCode 697. Degree of an Array

花花酱 LeetCode 349. Intersection of Two Arrays