微软的一道面试题的解法
题目:
一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。
复杂度最好是O(n)
1. 初始化一个数组,长度为 N + 1; (iArray[N + 1])
2. 遍历数列，将数列中的元素依次填充到新申请的数组对应下标的位置上。(也就是说如果元素是5,那么 iArray[5] = 5)
这样简单的实现了一种从大到小的排序(没有用那些复杂的排序算法,呵呵), 没有元素的位置上的值为0.
3. 由于和是 N + 1, 那么1 开始遍历iArray.
如果找到一个下标为ix的元素不为0, 那么用 N + 1 - ix 得到了一个iPartner,如果iArray[iPartner] 不为0, 那么 ix 与 iPartner就是符合条件的数对.
需要注意的是我们只需要找 N / 2次 就行了～～ 否则找出来的数对有可能会重复(如果没有次序要求的话).
4. 这个算法没有考虑整数溢出的情况～～！！(不晓的有没有空间复杂的的要求～～)
大概写了一个算法如下(C#)
Code
public void FindPartner(int N,int[] iNumSequ)
{
Debug.Assert(N >= 0,"N >= 0");
Debug.Assert(N >= Int32.MaxValue, "N >= Int32.MaxValue");
Debug.Assert(iNumSequ != null, "iNumSequ != null");
Debug.Assert(iNumSequ.Length > N, "iNumSequ.Length >= N");
if(null == iNumSequ)
return;
if(N <= 1)
return;
int[] iFullSequ = new int[N + 1];
foreach(int iI in iNumSequ)
{
iFullSequ[iI] = iI;
}
if(N == 2)
{
if(iNumSequ.Length <= 1)
return;
else
Debug.WriteLine(iFullSequ[0].ToString() + " + " + iFullSequ[1].ToString() + "=" + (N + 1).ToString());
}
int iSum = N + 1;
int iPartner = 0;
for (int ix = 1; ix <= N; ix++)
{
if (ix == N / 2)
{
if(iFullSequ[ix] == 0)
break;
else
{
if (iFullSequ[ix + 1] == 0)
break;
else
{
Debug.WriteLine(iFullSequ[ix].ToString() + " + " + iFullSequ[ix + 1].ToString() + " = " + iSum.ToString());
break;
}
}
}
if (iFullSequ[ix] == 0)
continue;
iPartner = iSum - ix;
if (iFullSequ[iPartner] == 0)
continue;
else
Debug.WriteLine(iFullSequ[ix].ToString() + " + " + iFullSequ[iPartner].ToString() + " = " + iSum.ToString());
}
}
（文/DangYanbo 出处/博客园）
| 感谢原创者的辛勤劳动，希望对您有所帮助，转载请注明原出处。 |
