Posts tagged as “unique”

花花酱 LeetCode 368. Largest Divisible Subset

By zxi on April 4, 2025

也算是一道比较经典的DP题了，需要找到一个最大的子集，使得其中元素两两的余数为0。

我们假设有一个集合为{a1, a2, a3, …, an}, {a1 < a2 < … < an)

如果 a2 % a1 = 0, a3 % a2 == 0, 那么a3 % a1 一定也等于0。也就是说a2是a1的倍数，a3是a2的倍数，那么a3一定也是a1的倍数。所以我们并不需要测试任意两个元素之间的余数为0，我们只需要检测a[i]是否为a[i-1]的倍数即可，如果成立，则可以确保a[i]也是a[i-2], a[i-3], … a[1]的倍数。这样就可以大大降低问题的复杂度。

接下来就需要dp就发挥威力了。我们将原数组排序，用dp[i]来表示以a[i]结尾（集合中的最大值），能够构建的子集的最大长度。

转移方程：dp[j] = max(dp[j], dp[i] + 1) if nums[j] % nums[i] = 0.

这表示，如果nums[j] 是 nums[i]的倍数，那么我们可以把nums[j]加入以nums[i]结尾的最大子集中，构建一个新的最大子集，长度+1。当然对于j，可能有好多个满足条件的i，我们需要找一个最大的。

举个例子：
nums = {2, 3, 4, 12}
以3结尾的最大子集{3}，长度为1。由于12%3==0，那么我们可以把12追加到{3} 中，构成{3,12}。
以4结尾的最大子集是{2,4}，长度为2。由于12%4==0，那么我们可以把12追加到{2,4} 中，构成{2,4,12} 。得到最优解。

这样我们只需要双重循环，枚举i，再枚举j (0 <= i < j)。时间复杂度：O(n^2)。空间复杂度：O(n)。

最后需要输出一个最大子集，如果不记录递推过程，则需要稍微判断一下。

class Solution {

public:

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

const int n = nums.size();

sort(begin(nums), end(nums));

// dp[i] = max size of subset ends with nums[i]

vector<int> dp(n);

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

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

if (nums[j] % nums[i] == 0)

dp[j] = max(dp[j], dp[i] + 1);

int s = *max_element(begin(dp), end(dp));

vector<int> ans;

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

if (dp[i] == s && (ans.empty() || ans.back() % nums[i] == 0)) {

ans.push_back(nums[i]);

--s;

}

return ans;

}

};

花花酱 LeetCode 2009. Minimum Number of Operations to Make Array Continuous

By zxi on November 26, 2021

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

All elements in nums are unique.
The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make numscontinuous.

Example 1:

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Example 2:

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3:

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Solution: Sliding Window

Remove duplicates and sort the numbers.
Try using nums[i] as the min number of the final array.
window [i, j), max – min < n, then change the rest of array to fit into or append after the window, which takes n – (j – i) steps.
e.g. input = [10, 3, 1, 4, 5, 6, 6, 6, 11, 15] => sorted + unique => [1, 3, 4, 5, 6, 10, 11, 15]
n = 10, window = [3, 4, 5, 6, 10, 11], max = 11, min = 3, max – min = 8 < 10
Final array = [3, 4, 5, 6, 1->7, 6₂->8, 6₃->9, 10, 11, 15->12]
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& A) {

const int n = A.size();

sort(begin(A), end(A));

A.erase(unique(begin(A), end(A)), end(A));

int ans = INT_MAX;

for (int i = 0, j = 0, m = A.size(); i < m; ++i) {

while (j < m && A[j] < A[i] + n) ++j;

ans = min(ans, n - (j - i));

}

return ans;

}

};

花花酱 LeetCode 1748. Sum of Unique Elements

By zxi on February 6, 2021

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.

Return the sum of all the unique elements of nums.

Example 1:

Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Example 3:

Input: nums = [1,2,3,4,5]
Output: 15
Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int sumOfUnique(vector<int>& nums) {

vector<int> seen(101);

int ans = 0;

for (int x : nums)

++seen[x];

for (int x : nums)

if (seen[x] == 1) ans += x;

return ans;

}

};

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

}

};