Posts tagged as “unique”

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

}

};

花花酱 LeetCode 95. Unique Binary Search Trees II

By zxi on March 7, 2018

Problem

https://leetcode.com/problems/unique-binary-search-trees-ii/description/

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

Idea: Recursion

for i in 1..n: pick i as root,
left subtrees can be generated in the same way for n_l = 1 … i – 1,
right subtrees can be generated in the same way for n_r = i + 1, …, n
def gen(s, e):
return [tree(i, l, r) for l in gen(s, i – 1) for r in gen(i + 1, e) for i in range(s, e+1)

# of trees:

n = 0: 1
n = 1: 1
n = 2: 2
n = 3: 5
n = 4: 14
n = 5: 42
n = 6: 132
…
Trees(n) = Trees(0)*Trees(n-1) + Trees(1)*Trees(n-2) + … + Tress(n-1)*Trees(0)

Time complexity: O(3^n)

Space complexity: O(3^n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<TreeNode*> generateTrees(int n) {

if (n == 0) return {};

const auto& ans = generateTrees(1, n);

cout << ans.size() << endl;

return ans;

}

private:

vector<TreeNode*> generateTrees(int l, int r) {

if (l > r) return { nullptr };

vector<TreeNode*> ans;

for (int i = l; i <= r; ++i)

for (TreeNode* left : generateTrees(l, i - 1))

for (TreeNode* right : generateTrees(i + 1, r)) {

ans.push_back(new TreeNode(i));

ans.back()->left = left;

ans.back()->right = right;

}

return ans;

}

};

Java

// Author: Huahua 4 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

return generateTrees(1, n);

}

private List<TreeNode> generateTrees(int l, int r) {

List<TreeNode> ans = new ArrayList<>();

if (l > r) {

ans.add(null);

return ans;

}

for (int i = l; i <= r; ++i)

for (TreeNode left : generateTrees(l, i - 1))

for (TreeNode right: generateTrees(i + 1, r)) {

TreeNode root = new TreeNode(i);

root.left = left;

root.right = right;

ans.add(root);

}

return ans;

}

Python 3

"""

Author: Huahua

Running time: 84 ms

"""

class Solution:

def generateTrees(self, n):

def newTree(x, l, r):

t = TreeNode(x)

t.left = l

t.right = r

return t

def gen(s, e):

return [newTree(i, l, r) for i in range(s, e + 1) for l in gen(s, i - 1) for r in gen(i + 1, e)] or [None]

return gen(1, n) if n > 0 else []

Solution 2: DP

Java

// Author: Huahua, 3 ms

class Solution {

public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<TreeNode>();

List<TreeNode>[] dp = new List[n + 1];

dp[0] = new ArrayList<TreeNode>();

dp[0].add(null);

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

dp[i] = new ArrayList<TreeNode>();

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

for (TreeNode left : dp[j])

for (TreeNode right: dp[i - j - 1]) {

TreeNode root = new TreeNode(j + 1);

root.left = left;

root.right = clone(right, j + 1);

dp[i].add(root);

}

return dp[n];

}

private TreeNode clone(TreeNode root, int delta) {

if (root == null) return root;

TreeNode node = new TreeNode(root.val + delta);

node.left = clone(root.left, delta);

node.right = clone(root.right, delta);

return node;

}

Posts tagged as “unique”

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

Solution: Sliding Window

C++

花花酱 LeetCode 1748. Sum of Unique Elements

Solution: Hashtable

C++

花花酱 LeetCode 945. Minimum Increment to Make Array Unique

Problem

Solution: Greedy

C++

Python3

花花酱 LeetCode 349. Intersection of Two Arrays

花花酱 LeetCode 95. Unique Binary Search Trees II

Problem

Idea: Recursion

C++

Java

Python 3

Solution 2: DP

Java

Related Problems