Find the missing numbers
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.zzzyk.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.
补充：软件开发 , C++ ,
