LeetCode-array类总结(会持续更新...)

本文主要是对leetcode中的array类算法的总结,包含了各题的solution和常用的解决方法。

相关源码:code

此类题的常用思路:

1
2
3
4
5
6
if 数组是否有序:
try 双指针法
try 反向计算
else:
try 集合数据结构
try 打表法

119. Pascal’s Triangle II

Description:

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

我的解题思路是:有点动态规划的感觉,运用杨辉三角的特性:当前值 = 上层正对的值 + 上层正对前一个值。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> result(rowIndex+1, 1);
vector<int> temp(rowIndex+1, 1);
for(int i = 0; i<rowIndex; i++){
for(int j = 1; j <= i; j++){
result[j] = temp[j] + temp[j-1];
}
for(int m=0; m<=rowIndex; m++){
temp[m] = result[m];
}
}
return result;
}
};

下面有一个更好的解题思路:大致思路和我上面的差不多,只不过是反向计算的。这样做有个好处:减少空间分配。反向操作是array类解决方案中经常使用到的trick。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> vi(rowIndex + 1);
vi[0] = 1;
for (int i = 0; i <= rowIndex ; ++i)
{
for (int j = i; j > 0; --j)
{
vi[j] = vi[j] + vi[j-1];
}
}
return vi;
}
};

167. Two Sum II - Input array is sorted

Description:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

解题思路:使用集合数据结构unordered_map<int, int>,一种map结构,find操作时间复杂度为O(1). 我们将数组中的元素逐个存入map,在存入的过程中检测是否有满足的元素;如果没有,就直接存入map.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
vector<int> twoSum(vector<int>& numbers, int target){
vector<int> result;
unordered_map<int, int> hash;
for(int i=0; i < numbers.size(); i++){
int temp = target - numbers[i];
if(hash.find(temp) != hash.end()){
result.push_back(hash.find(temp)+1);
result.push_back(i+1);
break;
}
hash[numbers[i]] = i;
}
return result;
}
};

解题思路二:使用两个指针,一个从左出发,一个从有出发。因为本题使用的数组是有序的,所以这么做是有效的。用这两个指针去适配target。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> result;
int l = 0;
int r = numbers.size()-1;
while(l < r){
int sum = numbers[l]+numbers[r];
if(sum == target){
result.push_back(l+1);
result.push_back(r+1);
break;
}else if(sum > target){
r--;
}else if(sum < target){
l++;
}
}
return result;
}
};

1. Two Sum

Description:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路:和上一题一样,但本题的数组有可能是无序的,因此,我们使用集合数据结构unordered_map。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
unordered_map<int, int> hash;
for(int i = 0; i<nums.size(); i++){
int lag = target - nums[i];
if(hash.find(lag) != hash.end()){
result.push_back(hash[lag]);
result.push_back(i);
break;
}
hash[nums[i]] = i;
}
return result;
}
};

219. Contains Duplicate II

Description:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

解题思路:本题要求数组相等的两个元素下标不超过k. 如果根据题意直接解,那么时间复杂度为O(n^2). 由于数组是无序的,我们倾向于使用集合数据结构。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if(nums.size() < 2 || k < 1){
return false;
}
unordered_map<int, int> hash;
bool flag = false;
for(int i=0; i<nums.size(); i++){
if(hash.find(nums[i]) != hash.end()){
if(i - hash[nums[i]] <= k){
flag = true;
break;
}
}
hash[nums[i]] = i;
}
return flag;
}
};

414. Third Maximum Number

Description:

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

1
2
3
4
5
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.

Example 2:

1
2
3
4
5
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

1
2
3
4
5
6
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

解题思路:我们看到测试用例中有重复的元素,并且无序。我们考虑使用集合数据结构,加之要求输出的结果是有序的。我们最终使用有序的集合数据结构set.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int thirdMax(vector<int>& nums) {
set<int> bag;
for(int i=0; i<nums.size(); i++){
bag.insert(nums[i]);
if(bag.size() > 3){
bag.erase(bag.begin());
}
}
return bag.size() == 3 ? *bag.begin() :*bag.rbegin();
}
};

448. Find All Numbers Disappeared in an Array

Description:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

解题思路:根据题意直接解的话,时间复杂度会为O(n^2)。我们就用空间换时间,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> result;
vector<int> extra(nums.size(), 0);
for(int i = 0 ; i<nums.size(); i++){
extra[nums[i]-1]++;
}
for(int i = 0; i<nums.size(); i++){
if(extra[i]==0){
result.push_back(i+1);
}
}
return result;
}
};

561. Array Partition I

Discription:

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

1
2
3
4
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

解题思路:总结规律,发现已排序数组的奇数项的和就是答案,这个可以通过反证法进行证明。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int sum = 0;
for(int i =0; i<nums.size();i+=2){
sum += nums[i];
}
return sum;
}
};

解题思路二:上面这种解法时间复杂度是O(nlogn),下面有种O(n)的解法。根据题目提示,给出了数据范围,并且数据无序,我们可以使用集合数据结构,只不过这次使用自己构造的数据结构打表法。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
vector<int> hashtable(20001,0);
for(size_t i=0;i<nums.size();i++)
{
hashtable[nums[i]+10000]++;
}
int ret=0;
int flag=0;
for(size_t i=0;i<20001;){
if((hashtable[i]>0)&&(flag==0)){
ret=ret+i-10000;
flag=1;
hashtable[i]--;
}else if((hashtable[i]>0)&&(flag==1)){
hashtable[i]--;
flag=0;
}else i++;
}
return ret;
}
};

581. Shortest Unsorted Continuous Subarray

Description:

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

1
2
3
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

解题思路:本题数组部分有序,我们使用双指针,这有个小trick:左右两个指针同时前进,不像之前根据某个状态,单独调节单个指针。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int length = nums.size();
int beg = -1;
int end = -2;
int max = nums[0];
int min = nums[length-1];
for(int i=1; i<length; i++){
max = max<nums[i]?nums[i]:max;
min = min>nums[length-i-1]?nums[length-i-1]:min;
if(max>nums[i]) end=i;
if(min<nums[length-i-1]) beg=length-i-1;
}
return end-beg+1;
}
};

66. Plus One

Description:

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

解题思路:总结规律,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
vector<int> plusOne(vector<int>& digits){
int n = digits.size();
for(int i = n-1; i>=0; i--){
if(digits[i] == 9){
digits[i] = 0;
}else{
digits[i]++;
return;
}
}
digits[0] = 1;
digits.push_back(0);
return digits;
}
};

88. Merge Sorted Array

Description:

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

解题思路:本题是两个有序的数组,我们要利用这一点,并且有个trick:反向计算。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){
int i = m-1;
int j = n-1;
int k = m+n-1;
while(i>=0 && j>=0){
if(nums1[i] > nums2[j]){
nums1[k--] = nums1[i--];
}else{
nums1[k--] = nums2[j--];
}
}
while(j>=0){
nums1[k--] = nums2[j--];
}
}
}

118. Pascal’s Triangle

Description:

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

1
2
3
4
5
6
7
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

解题思路:本题考察杨辉三角的性质,我们直接利用性质进行解题。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> result(numRows);
for(int i=0; i < numRows; i++){
result[i].resize(i+1);
for(int j=0; j<=i; j++){
if(j==i || j==0){
result[i][j] = 1;
}else{
result[i][j] = result[i-1][j] + result[i-1][j-1];
}
}
}
return result;
}
};

121. Best Time to Buy and Sell Stock

Description:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

1
2
3
4
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

1
2
3
4
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.

解题思路:观察本题规律,局部有序,关键点是判断极小值点。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2){
return 0;
}
int result = 0;
int min = 0;
for(int i=0; i< prices.size()-1; i++){
if(prices[i+1] > prices[i]){
if(prices[i+1]-prices[min] > result){
result = prices[i+1]-prices[min];
}
}else{
if(prices[i+1] < prices[min]){
min = i+1;
}
}
}
return result;
}
};

605. Can Place Flowers

Description:

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

1
2
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

1
2
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

  1. The input array won’t violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. n is a non-negative integer which won’t exceed the input array size.

解题思路:根据本题题意直接作答,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = 0;
for(int i=0; i<flowerbed.size(); i++){
if(flowerbed[i] == 0){
int next = (i==flowerbed.size()-1) ? 0 : flowerbed[i+1];
int pre = (i==0) ? 0 : flowerbed[i-1];
if(next == 0 && pre == 0){
flowerbed[i] = 1;
count++;
}
}
}
return count>=n;
}
};

189. Rotate Array

Description:Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
for(int i=0; i<k;i++){
int temp = nums[n-1];
nums.pop_back();
nums.insert(nums.begin(), temp);
}
}
};

35. Search Insert Position

Description:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
for(int i=0; i<nums.size(); i++){
if(i==0 && nums[0] > target){
return 0;
}
if(nums[i] - target == 0){
return i;
}
if(nums[i] > target){
return i;
}
}
return nums.size();
}
};

53. Maximum Subarray

Description:Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

解题思路:本题很经典,使用动态规划,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size() == 0){
return 0;
}
if(nums.size() == 1){
return nums[0];
}
int sum = 0;
int max = nums[0];
for(int i=0; i<nums.size(); i++){
//sum += nums[i];
if(sum <= 0){
sum = nums[i];
}else{
sum+= nums[i];
}
max = max > sum ? max:sum;
}
return max;
}
};

665. Non-decreasing Array

Description:

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

1
2
3
Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

1
2
3
Input: [4,2,1]
Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.

Note: The n belongs to [1, 10,000].

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
for(int i=1; i<nums.size() && count<=1; i++){
if(nums[i-1] > nums[i]){
count++;
if(i-2<0 || nums[i-2] < nums[i]){
nums[i - 1] = nums[i];
}else{
nums[i] = nums[i-1];
}
}
}
return count<=1;
}
};

532. K-diff Pairs in an Array

Description:

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:

1
2
3
4
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

1
2
3
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

1
2
3
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won’t exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

解题思路:本题有很强技巧性,使用了两个集合数据结构:map和set,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int findPairs(vector<int>& nums, int k) {
if(k < 0){
return 0;
}
unordered_map<int, int> slot;
unordered_set<int> result;
for(int i=0; i<nums.size(); i++){
if(slot.count(nums[i] - k)){
result.insert(nums[i]-k);
}
if(slot.count(nums[i] + k)){
result.insert(nums[i]);
}
slot[nums[i]] +=1;
}
return result.size();
}
};

643. Maximum Average Subarray I

Description:Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

1
2
3
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int sum = 0;
int max = 0;
for(int i=0; i<nums.size(); i++){
if(i<k){
sum += nums[i];
max = sum;
}else{
sum = sum+nums[i]-nums[i-k];
max = max > sum ? max : sum;
}
}
return max/(float)k;
}
double findMaxAverage2(vector<int>& nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
int max = sum;
for (int i = k; i < nums.size(); i++) {
sum += nums[i] - nums[i - k];
max = max > sum ? max : sum;
}
return max / 1.0 / k;
}
};

628. Maximum Product of Three Numbers

Description:

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

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

Example 2:

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

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(),nums.end());
int len = nums.size();
int temp1 = nums[len-1]*nums[0]*nums[1];
int temp2 = nums[len-1]*nums[len-2]*nums[len-3];
return temp1>temp2?temp1:temp2;
}
};

566. Reshape the Matrix

Description:

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

1
2
3
4
5
6
7
8
9
10
Input:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
Output:
[[1,2],
[3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:

  1. The height and width of the given matrix is in range [1, 100].
  2. The given r and c are all positive.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int row = nums.size();
int col = nums[0].size();
if(row*col != r*c){
return nums;
}
vector<vector<int>> result(r);
for(int i=0; i<r;i++){
result[i].resize(c);
}
for(int i=0; i<row*col; i++){
result[i/c][i%c] = nums[i/col][i%col];
}
//delete result;
return result;
}
};

645. Set Mismatch

Description:The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

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

Note:

  1. The given array size will in the range [2, 10000].
  2. The given array’s numbers won’t have any order.

解题思路:代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int[] res = new int[2];
for (int i : nums) {
if (nums[Math.abs(i) - 1] < 0) res[0] = Math.abs(i);
else nums[Math.abs(i) - 1] *= -1;
}
for (int i=0;i<nums.length;i++) {
if (nums[i] > 0) res[1] = i+1;
}
return res;
}
};