数组-缺失的元素

2019-05-26
#Coding-Data View

数组-缺失的元素

448. Find All Numbers Disappeared in an Array

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

mark elements as negative using nums[nums[i] -1] = -nums[nums[i]-1].

这样，所有以见过的元素作为索引的值将被标为负数。

再做一次循环，如果这个数为正，说明在上一次循环中没有以这个数为下标标记过。把i+1作为值插入到结果vec中。

注意与442. Find All Duplicates in an Array的区别。

268. Missing Number

a ^ a = 0 b ^ 0 = b

163. Missing Ranges

如何处理缺失的是一个元素和一个范围

1
2
3
4
5
6
7
for(int i = 1; i < N; ++i ) 
{
    if(nums[i] - nums[i-1] != 1)
        cout << nums[i] - 1 << endl;
}
if(nums[N-1] != upper) cout << upper << endl;

上面这段代码可以输出缺失范围的右端点，左端点怎么处理？

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
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> res;
        int N = nums.size();
        
        if(N == 0) {
            if(lower != upper)
                res.push_back(to_string(lower) + "->" + to_string(upper));
            else
                res.push_back(to_string(lower));
            return res;
        } 
        if(nums[0] != lower) {
            if(nums[0]-1 != lower) {
                res.push_back(to_string(lower) + "->" + to_string(nums[0] - 1));
            }
            else {
                res.push_back(to_string(lower));
            }
        }
        for(int i = 1; i < N; ++i ) {
            if(nums[i-1] + 1 != nums[i]) {
                if ( nums[i] - nums[i - 1] ==  2) {
                    res.push_back(to_string(nums[i - 1] + 1));
                }
                else {
                    res.push_back(to_string(nums[i - 1] + 1) + "->" + to_string(nums[i] - 1));
                }
            }
        }
        if(nums[N-1] != upper) {
            if(nums[N - 1] + 1 != upper) {
                res.push_back(to_string(nums[N - 1] + 1) + "->" + to_string(upper));
            }
            else {
                res.push_back(to_string(upper));
            }
        }
        return res;
    }
};

有int溢出的问题；

Input:

1
2
3
[-2147483648,-2147483648,0,2147483647,2147483647]
-2147483648
2147483647

统一处理了单个数字和范围的情况

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:
    string get_range(int start, int end)
    {
        return start==end? to_string(start) : to_string(start)+"->"+to_string(end);
    }
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<string> res;
        long int pre = (long)lower-1;
        
        if(nums.size()<=0)
        {
            res.push_back(get_range(lower,upper));
            return res;
        }   
        
        for(int i =0; i <= nums.size(); i++)
        {
           long int cur = (i==nums.size()? (long)upper+1:(long)nums[i]);
           if(cur-pre>=2)
               res.push_back(get_range(pre+1,cur-1));
            pre = cur;
        }
        return res;
    }
};

Comments: