Question: Design and implement an algorithm (C++ function) that, given an array of integers 0 to 2n-1 with two values missing, determines (and displays) the two missing integers. For example, if n is 3, the given integers might be {0,1,3,4,5,7}, so the output would be 2 and 6. Note that the given integers are in ordered. You may assume there are no duplicate values in the array. What is the runtime of your algorithm? What is the memory requirement of your algorithm? test IDE: Microsoft Visual Studio 2005 test OS:Microsoft Windows 7 The code as following may solve this problem: [cpp] // MissingNumber.cpp : 定義控制台應用程序的入口點。 // #include "stdafx.h" #include <cstdio> int _tmain(int argc, _TCHAR* argv[]) { int nCount; printf("Input N:"); scanf("%d", &nCount); nCount *= 2; int iComp =0; int *pData = new int[nCount]; printf("Input numbers:"); for(int i = 0;i < nCount; ++i) { scanf("%d", &pData[i]); } const int MAX_NUM = nCount + 1; printf("The missing numbers are:"); // note the loop criterion, it can help you to work till the upbound for(int i = 0;i < nCount || iComp <= MAX_NUM;) { if (pData[i] == iComp) { ++iComp; ++i; } else { printf("%d ", iComp); ++iComp; } } return 0; } // MissingNumber.cpp : 定義控制台應用程序的入口點。 // #include "stdafx.h" #include <cstdio> int _tmain(int argc, _TCHAR* argv[]) { int nCount; printf("Input N:"); scanf("%d", &nCount); nCount *= 2; int iComp =0; int *pData = new int[nCount]; printf("Input numbers:"); for(int i = 0;i < nCount; ++i) { www.2cto.com scanf("%d", &pData[i]); } const int MAX_NUM = nCount + 1; printf("The missing numbers are:"); // note the loop criterion, it can help you to work till the upbound for(int i = 0;i < nCount || iComp <= MAX_NUM;) { if (pData[i] == iComp) { ++iComp; ++i; } else { printf("%d ", iComp); ++iComp; } } return 0; } Analysis:The runtime complexity is O(n) and the memory requirement is O(1). Thinking: What if the given integers are in any order ? A resolution may work out to the thinking: You can use quick sort before finding the missing integers.
