程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 61. 從1到n，共有n個數字，每個數字只出現一次。從中隨機拿走一個數字x，請給出最快的方法，找到這個數字。如果隨機拿走k(k>=2)個數字呢？[find k missing numbers from 1 to n]

61. 從1到n，共有n個數字，每個數字只出現一次。從中隨機拿走一個數字x，請給出最快的方法，找到這個數字。如果隨機拿走k(k>=2)個數字呢？[find k missing numbers from 1 to n]

編輯：C++入門知識

【本文鏈接】

http://www.cnblogs.com/hellogiser/p/find-k-missing-numbers-from-1-to-n.html

【題目】

從1到n，共有n個數字(無序排列)，每個數字只出現一次。現在隨機拿走一個數字x，請給出最快的方法，找到這個數字。要求時間復雜度為O(n)，空間復雜度為O(1)。如果隨機拿走k(k>=2)個數字呢？

【分析】

題目給出的條件很強，數字是從1~n的數字，限制了數字的范圍；每個數字只出現一次，限制了數字出現的次數；隨即拿走了一個數字，說明只有一處是與其他不同、不符合規律的。我們可以利用這些特點來選擇合適的解法。

(1)Hash法。利用Hash法統計數字出現的次數，次數為0的即為所求。時間復雜度O(n)，空間復雜度O(n)。通常這不是面試、筆試時想要的答案，但是Hash的優勢在於其通用性。

(2)排序法。利用快排，得到排序後的數組，然後順序遍歷，統計次數為0的數字。時間復雜度O(nlgn)，空間復雜度O(1)。其時間復雜度略高，通常也不是面試官期待的解法，但排序法也算是一種通用做法。

(3)元素相乘/相加法。時間復雜度O(n)，空間復雜度O(1)。

元素相乘法：由於只有一個元素被拿走，因此我們只需要先算出n的階乘n!，再除以現存所有數字的乘積M，即可得到拿走的數字x (x=n!/M)。但是且缺陷是n不能太大，否則會溢出。

元素相加法：先算出從1到n的所有數字的和Sn，然後減去現有所有數字的和sum，即可得到拿走的數字x(x=Sn-sum)。元素相加法比元素相乘要更好一些。

(4)位運算。時間復雜度O(n)，空間復雜度O(1)。

位運算法如果可以使用的話，應該是計算最快的方法。但是位運算對條件要求也較苛刻，一般需要元素有特殊規律，才有可能使用這種方法。在本題目中，對1~n所有元素進行xor運算得到A=1^2^3^…^(x-1)^x^(x+1)^…^n，在對取走一個元素後剩下的元素進行xor運算得到B=1^2^3^…^(x-1)^(x+1)^…^n，二者xor即可得拿走的數字x = A^B。因為在A^B的過程中相同的數字都被抵消掉了，剩余的結果即為x。

【代碼】

C++ Code 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84 // 61_FindMissingNumberFrom1toN.cpp : Defines the entry point for the console application.
//
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/5/28
*/

#include "stdafx.h"

/*
A=1^2^3^...^(x-1)^x^(x+1)^...^n
B=1^2^3^...^(x-1)^(x+1)^...^n
x = A^B

n=9
1,2,3,4,6,7,8,9
x = 5
*/
int FindMissingNumberFrom1ToN(int data[], int n)
{
    int length = n - 1;
    if(NULL == data || length <= 0)
        return -1;
    // xor all
    int xor_all = 0;
    for(int i = 1; i <= n; i++)
        xor_all ^= i;

    // xor of current array
    int xor_current = 0;
    for(int i = 0; i < length; i++)
        xor_current ^= data[i];

    //get result
    int result = xor_all ^ xor_current;
    return result;
}

void test_base(int data[], int n)
{
    int result = FindMissingNumberFrom1ToN(data, n);
    printf("%d \n", result);
}

void test_case1()
{
    int data[] = {1, 2, 3};
    int length = sizeof(data) / sizeof(int);
    test_base(data, length + 1);
}

void test_case2()
{
    int data[] = {2, 3, 4};
    int length = sizeof(data) / sizeof(int);
    test_base(data, length + 1);
}

void test_case3()
{
    int data[] = {1, 2, 3, 4, 6, 7, 8, 9};
    int length = sizeof(data) / sizeof(int);
    test_base(data, length + 1);
}

void test_main()
{
    test_case1();
    test_case2();
    test_case3();
}

int _tmain(int argc, _TCHAR *argv[])
{
    test_main();
    return 0;
}
/*
4
1
5
*/

【擴展】

如果隨機拿走兩個數字呢？如果隨機拿走k(k>2)個數字呢？

（1）（2）是通用做法，仍適合。

（3）擴展：

K=1時，構造2個等式。

Sa = 1+2+…(x-1)+x+(x+1)…+n

Sb = 1+2+…(x-1)+(x+1)…+n

X = Sa-Sb

K=2時，構造4個等式。

S2a = 1²+2²+…+x²+…+y²+…+n

S2b = 1²+2²+…(x-1)²+(x+1)²…+(y-1)²+(y+1)²…+n

S1a = 1+2+…+x+…+y+…+n