3.1 Distribute candie’s

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor’s advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Example 1:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.
Copy the code

Example 2:

Input: candyType = [1,1,2,3] Output: 2 Explanation: Alice can only eat 4/2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3] she still can only eat 2 different types.Copy the code

Example 3:

Input: candyType = [6,6,6] Output: 1 Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.Copy the code

Constraints:

n == candyType.length
2 <= n <= 104
n is even.
-105 <= candyType[i] <= 105
Copy the code

Second, the solution is as follows, the idea is not complicated, not much explanation:

var distributeCandies = function(candyType) {
    return Math.min(candyType.length/2,new Set(candyType).size)
};
Copy the code

3.2 Set Mismatch

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]
Copy the code

Example 2:

Input: nums = [1,1]
Output: [1,2]
Copy the code

Constraints:

2 <= nums.length <= 104
1 <= nums[i] <= 104
Copy the code

I had a lot of ideas at the beginning of this problem, but binary search didn’t seem to be suitable for this problem, so I wrote O(n) solution, feeling a little stiff:

var findErrorNums = function(nums) { let ans = []; let cnt = new Set(); for (let i of nums){ cnt.has(i)? ans.push(i):cnt.add(i); } for (let i=1; i<=nums.length; i++){ if (! cnt.has(i)) ans.push(i) } return ans };Copy the code

(a+b)/2 (b-a)/2 (b-a)/2 (b-a)/2 (b-a)/2

var findErrorNums = function(nums) {
    let n = nums.length;
    let A = n*(n+1)/2, B = n*(n+1)*(2*n+1)/6;
    for (let i of nums){
        A -= i;
        B -= i*i;
    }
    return [(B-A*A)/2/A, (B+A*A)/2/A]
};        
Copy the code

3.3 Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Copy the code

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Copy the code

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Copy the code

Example 4:

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.
Copy the code

Constraints:

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
All the numbers of nums are unique.
Copy the code

Can I write a space complexity O(1), time complexity O(n) algorithm, which directly prompt me to write the following method, using an arithmetic sequence summation formula, do the subtraction to get the missing value, is not the best but there is not much room for optimization, so I will not translate others’ problem:

var missingNumber = function(nums) {
    let sum = (nums.length+1)*nums.length/2;
    for (let i of nums){
        sum -= i
    }
    return sum
};
Copy the code