內容
給您 T 個打亂的等差數列，請你找出數列中少了的數字，以及重複的數字。
輸入
測資第一列有個數字 T , T <= 200
以下有 T 個打亂的數列，請找出遺失的數 m , 重複的數 d
數列長度 >= 5
min < m < max
min <= d <= max
2
7 9 1 3 7
5000 8000 9000 8000 7000
輸出
輸出 m 和 d
5 7
6000 8000
解題思路
將輸入字串轉成整數排序，根據題意，m 不會為最大或最小項，所以等差即是 (min + max) / (len - 1)
有等差之後從第二個元素開始遍歷陣列，如果發現不符合等差規則的話再判斷是重複出現的或是缺少數字即可。
完整程式碼
AC (3ms, 112KB)
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000
int kase, list[1000], tmp, nLen, gap, same, miss;
char input[MAX], ans;
int cmp(const int* lhs, const int* rhs)
{
return *lhs - *rhs;
}
void setDigitList()
{
tmp = nLen = 0;
for (int i = 0; input[i]; i++)
{
if (input[i] == ' ')
list[nLen++] = tmp, tmp = 0;
else
tmp = (tmp << 3) + (tmp << 1) + (input[i] - '0');
}
list[nLen++] = tmp;
}
int main()
{
scanf(" %d", &kase);
getchar();
while (kase--)
{
gets(input);
setDigitList();
qsort(list, nLen, sizeof(int), cmp);
gap = (list[nLen - 1] - list[0]) / (nLen - 1), ans = 0;
for (int i = 1; i < nLen; i++)
{
if (list[i] != list[i - 1] + gap)
{
if (list[i] == list[i - 1])
same = list[i], ans++;
else
miss = (list[i] + list[i - 1]) >> 1, ans++;
if (ans == 2)
break;
}
}
printf("%d %d\n", miss, same);
}
return 0;
}
|
