首页 > 试题广场 > 连续整数
[编程题]连续整数
  • 热度指数:4279 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
牛牛的好朋友羊羊在纸上写了n+1个整数,羊羊接着抹除掉了一个整数,给牛牛猜他抹除掉的数字是什么。牛牛知道羊羊写的整数神排序之后是一串连续的正整数,牛牛现在要猜出所有可能是抹除掉的整数。例如:
10 7 12 8 11 那么抹除掉的整数只可能是9
5 6 7 8 那么抹除掉的整数可能是4也可能是9

输入描述:
输入包括2行:
第一行为整数n(1 <= n <= 50),即抹除一个数之后剩下的数字个数
第二行为n个整数num[i] (1 <= num[i] <= 1000000000)


输出描述:
在一行中输出所有可能是抹除掉的数,从小到大输出,用空格分割,行末无空格。如果没有可能的数,则输出mistake
示例1

输入

2 3 6

输出

mistake

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //抹除一个数之后剩下的数字个数
        int[] num = new int[n];
        for (int i = 0; i < n; i ++) {
            num[i] = sc.nextInt();
        }
        //如果只有一个数字,注意保证输入正整数
        if (n == 1) {
            if (num[0] > 1) {
                System.out.println(num[0] - 1 + " " + (num[0] + 1));
                return;
            } else {
                System.out.println((num[0] + 1));
                return;
            }
        }
        //多个数字,先排序
        Arrays.sort(num);

        //如果有重复数字,则mistake
        for (int i = 0; i < n-1; i ++) {
            if (num[i] == num[i+1]) {
                System.out.println("mistake");
            }
        }
        //现在没有了重复数字,那么可以根据最大数num[n-1]和最小数num[0]的差值来比较,
        //这样去判断,中间数字是连续的,还是缺了一个,还是缺了多个
        if (num[n-1] - num[0] > n) {
            System.out.println("mistake");
        } else if (num[n-1] - num[0] == n) {
            for (int i = 0; i < n-1; i ++) {
                if (num[i] + 2 == num[i+1]) {
                    System.out.println(num[i] + 1);
                }
            }
        } else {
            if (num[0] > 1) {
                System.out.println(num[0] - 1 + " " + (num[n-1] + 1));
            } else {
                System.out.println((num[n-1] + 1));
            }
        }
    }
}


发表于 2017-03-12 14:08:09 回复(3)
#include<iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int min = 1000000001;
    int max = 0;
    int res = 0;
    int num = 0;
    for(int i = 0; i < n; i++) {
        cin>>num;
        if(num < min) min = num;
        if(num > max) max = num;
        res ^= num;
    }
    for(int i = min; i <= max; i++) {
        res ^= i;
    }
    if(res == 0) {
        if(min - 1> 0)
            cout<<min-1<<" "<<max+1;
        else cout<<max+1;
    }
    else if(res <= min || res >= max) {
        cout<<"mistake"<<endl;
    }
    else cout<<res;
}

编辑于 2017-03-08 17:31:26 回复(11)
思路:对串排序。然后用最大值减最小值,如果差为n,则涂抹的是中间数字;如果差为n-1,则涂抹两边数字;其他,mistake。先判断是否有重复数字。注意最小值为1的情况。
#include <set>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
vector<int> t_s;
cin >> n;
for (int i = 0; i < n; i++)
{
int tt;
cin >> tt;
t_s.push_back(tt);
}
sort(t_s.begin(), t_s.end());
set<int> s;
for (int j = 0; j < n; j++){
s.insert(t_s[j]);
}
if (s.size() == n)//判断是否有数重复
                    {
if (t_s[n - 1] - t_s[0] == n - 1)
{
                if(t_s[0]-1!=0){
cout << t_s[0] - 1 << ' ' << t_s[n - 1] + 1 << endl;}
                else cout <<t_s[n - 1] + 1 << endl;
}
else if (t_s[n - 1] - t_s[0] == n){

for (int k = t_s[0]; k <= t_s[n - 1]; k++)
{
if (s.count(k) == 0) {
cout << k << endl;
return 0;
}
}
}
            else cout << "mistake" << endl;
}
else cout << "mistake" << endl;
return 0;
}
编辑于 2017-03-08 15:20:50 回复(0)
发表于 2018-04-30 12:55:00 回复(0)
#我来用python写一个,见识一下python的强大 
def get_the_lose_one(data):
    data_ordered = sorted(data,lambda x,y:x-y)
    outcome=  []  for index,data in enumerate(data_ordered): if index == len(data_ordered)-2:  break  if data+1 != data_ordered[index+1]:
            outcome.append(data+1)  if len(outcome) >= 1:  print 'mistake'    elif not len(outcome):  print [data_ordered[0]-1,data_ordered[len(data_ordered)-1]+1]  else: print outcome[0]


发表于 2017-09-21 21:53:27 回复(1)
/*
参考的小风筝的答案,不过那个原答案不能通过所有测试用例,我加了个判断
*/


import java.util.Arrays;
import java.util.Scanner;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int[] num=new int[n];
for(int i=0;i<n;i++){
num[i]=sc.nextInt();
}
if(n==1){
if(num[0]>1){
System.out.println(num[0]-1+" "+(num[0]+1));
}else{
System.out.println((num[0]+1));
}
}
Arrays.sort(num);
for(int i=0;i<n-1;i++){
if (num[i] == num[i+1]) {
System.out.println("mistake");
}
}
if(num[n-1]-num[0]>n){
System.out.println("mistake");
}else if(num[n-1]-num[0]==n){
for (int i = 0; i < n-1; i ++) {
if (num[i] + 2 == num[i+1]) {
System.out.println(num[i] + 1);
}
}
}else{
if (num[0] > 1&&n!=1) {
System.out.println(num[0] - 1 + " " + (num[n-1] + 1));
} else if(num[0]!=1&&n!=1){
System.out.println((num[n-1] + 1));
}
}
if(num[0]==1&&num[n-1]==n&&n!=1){//如果n==1&&num[0]!=1
System.out.println((num[n-1] + 1));
}
}

}

发表于 2017-03-24 16:17:43 回复(0)
/*
	5种情况
	1、内缺:
		i. 缺1个  			直接输出结果 
		ii. 缺多个(间接)	mistake 
		iii.缺多个(连续) 	mistake 
	2、 外缺:
		i.第一个元素==1		数列右边缺 
		ii.第一个元素>1 	数列左右都有可能缺 
*/
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_ = 50;

int arr[MAX_];

int main() {
    int n,count = 0,tmp;
    
    cin >> n;
    
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    
    sort(arr,arr+n);
    
    for(int i=1; i<n; i++) {
        if(arr[i]-arr[i-1] == 2) {
            tmp = arr[i] - 1;
            count++;
            continue;
        } else if(arr[i]-arr[i-1] > 2) {	// 缺多个(连续) 
            cout << "mistake" << endl;
            return 0;
        }		
    }
    	
    if(count == 1) {				// 缺1个 
        cout << tmp << endl;
        return 0;
    } else if(count > 1) {			// 缺多个(间接) 
        cout << "mistake" << endl;
        return 0;
    }
    
    if(arr[0] > 1) {				// 数列左右都有可能缺 
        cout << arr[0]-1 << " " << arr[n-1]+1 << endl;
    } else {						// 数列右边缺 
        cout << arr[n-1]+1 << endl;
    }
    
    return 0;
}

发表于 2017-03-23 22:38:52 回复(1)
while True:
    list_get_str = input('请输入一串整数(以空格分隔)').split(' ')
    list_get = list(map(int, list_get_str))
    list_get.sort()
    print(list_get)

    list_length = len(list_get)
    count = 0
    count_list = []
    mistake = 0

    for i in range(list_length-1):
        if list_get[i] + 1 == list_get[i+1]:
            continue
        elif list_get[i] + 2 == list_get[i + 1]:
            count += 1
            count_list.append(list_get[i])
        elif (list_get[i] >= list_get[i+1])&nbs***bsp;(list_get[i] + 2) < list_get[i+1]:
            print('mistake')
            mistake = 1
            break

    if mistake == 0:
        if len(count_list) == 0 :
            print(list_get[0]-1)
            print(list_get[-1] + 1)
        elif len(count_list) == 1:
            print(count_list[0])
        elif len(count_list) >= 2:
            print('mistake')



编辑于 2020-08-26 22:28:16 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int length = in.nextInt();
        int[] numbers = new int[length];
        for (int i = 0; i<length; i++){
            numbers[i]=in.nextInt();
        }
        if(length==1) {
        	if(numbers[0]==1) {
        		System.out.println(2);
        	}
        	else {
        		System.out.print((numbers[0]-1) +" "+ (numbers[0]+1));
        	}
        }
        else {
        	 Arrays.sort(numbers);
             ArrayList<Integer> index = new ArrayList<Integer>();
                 for(int i = 0; i<length-1; i++){
                     if(numbers[i+1]-numbers[i]==0||numbers[i+1]-numbers[i]>2){
                             System.out.println("mistake");
                             return; 
                     }
                     if(numbers[i+1]-numbers[i]==2) {
                     	index.add(i);
                     }
                 }
                 if(index.size()==0) {
                	 if(numbers[0]==1) {
                		 System.out.print((numbers[length-1]+1));
                	 }
                	 else {
                		 System.out.print((numbers[0]-1) +" "+ (numbers[length-1]+1));
                	 }
                 }
                 else if (index.size()==1) {
                 	System.out.println(numbers[index.get(0)]+1);
                 }
                 else {
                 	System.out.println("mistake");
                 }
                          
         }
        }
       
}
那些年躲不过的坑!!!!
发表于 2020-04-03 08:34:52 回复(0)
#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
	void Swap(int& a, int& b)
	{
		a ^= b ^= a ^= b;
	}

	// 选择排序
	void SortVec(vector<int>& vec)
	{				
		int len = vec.size();
		if (len == 1)
		{
			return;
		}
		
		int minPos;
		for (size_t i = 0; i < len; i++)
		{
			minPos = i;
			for (size_t j = i + 1; j < len; j++)
			{
				if (vec[minPos] > vec[j])
				{
					minPos = j;
				}								
			}
			if (minPos != i)
			{
				Swap(vec[minPos], vec[i]);
			}			
		}		
	}
	
	void Func1(vector<int>& vec, int Num)
	{		
		// 1、先排序
		SortVec(vec);
		int gap = vec[Num - 1] - vec[0];
		// 涂抹中间数字
		if ( gap == Num)
		{
			for (size_t i = 0; i < Num; i++)
			{
				int gapTmp = vec[i + 1] - vec[i];
				if (gapTmp == 0)	// 如果有重复数字
				{
					cout << "mistake";
					return;
				}
				
				if (gapTmp != 1)
				{
					cout << vec[i] + 1;
					return;
				}				
			}			
		}
		else if ( gap == (Num - 1) )	// 涂抹两端数字
		{
			if (vec[0] == 1) cout << vec[Num - 1] + 1;	// 如果最小值为1, 涂抹的是最右边(1 <= num[i] <= 1000000000)
			else
			{
				cout << vec[0] - 1 << " " << vec[Num - 1] + 1;				
			}			
		}
		else
		{
			cout << "mistake";
		} 
	}
};

int main()
{
	Solution s;
	vector<int> vec;
	int Num;
	cin>>Num;
	for (size_t i = 0; i < Num; i++)
	{
		int num;
		cin >> num;
		vec.push_back(num);
	}
	s.Func1(vec, Num);

	return 0;
}

发表于 2019-09-07 22:53:01 回复(1)
#include <stdlib.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
using namespace std;
int partition(int a[], int low, int high) {
 int pivotPos = low;
 int pivot = a[low];
 int tmp;
 for (int i = low + 1; i <= high; ++i) {
  if (a[i] <= pivot) {
   ++pivotPos;
   if (i != pivotPos) {
    tmp = a[i];
    a[i] = a[pivotPos];
    a[pivotPos] = tmp;
   }
  }
 }
 a[low] = a[pivotPos];
 a[pivotPos] = pivot;
 return pivotPos;
}
void Qsort(int a[], int low, int high) {
 if (low < high) {
  int pivotPos = partition(a, low, high);
  Qsort(a, low, pivotPos - 1);
  Qsort(a, pivotPos + 1, high);
 }
}
int main() {
 int n;
 scanf("%d", &n);
 int* a = new int[n];
 for (int i = 0; i < n; ++i)
  scanf("%d", a + i);
 Qsort(a, 0, n - 1);
 int count = 0;
 int pos;
 for (int i = 0; i < n-1; ++i) {
  if (a[i + 1] - a[i] == 2) {
   pos = i;
   ++count;
  }
  else if (a[i + 1] - a[i] > 2)
   count += a[i + 1] - a[i] - 1;
  if (count > 1)
   break;
 }
 if (count > 1) {
  printf("mistake");
 }
 else if (count == 0) {
  if (a[0] - 1 != 0) {
   printf("%d ", a[0] - 1);
  }
  printf("%d", a[n - 1] + 1);
 }
 else {
  printf("%d", a[pos] + 1);
 }
 delete[]a;
 return 0;
}

发表于 2019-05-03 12:00:44 回复(0)
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);  int n,k,count=0;  n=sc.nextInt();  int[] a=new int[n];  for(int i=0;i<n ;i++)
            a[i]=sc.nextInt();  Arrays.sort(a);  k=a[0];//把排序后数组的第一个数赋值给一个常量  for(int i=1;i<n;i++)//计算有多少个相邻数字差值大于1的情况存在,并把数量计入count  { if(a[i]==a[i-1]+1) continue;  else count++;  } for(int i=0;i<n;i++,k++){//开始遍历数组,开始k的值和啊a[0]相同,每次k++寻找差值大于1的数  if(a[i]!=k&&a[i]==k+1&&count==1)//如果数组和k的值不相等,且整个数组中只有这一种情况存在(即count==1),则这个值为所求值  {
                System.out.print(k);  System.exit(0);  } else if(a[i]!=k&&a[i]!=k+1||count>1)//如果数组和k的值不相同,但是k和数组的差值大于1,则这种情况没有可能的数,并且如果count>1,也不存在  {
                System.out.print("mistake");  System.exit(0);  }
        }//整个数组是一个有序数列,如果所有数之间的差值都为1,则进行如下判断  if(a[0]==1) {//如果这个数组第一个数为1,则只可能是末尾丢失,所求数位数组最后一个数+1  System.out.print(a[n-1]+1);  } else System.out.print(a[0]-1+" "+(a[n-1]+1));//如果数组第一个数不是1,根据题意判断有两个值,即头-1尾+1  }
}
发表于 2019-02-28 14:54:12 回复(0)
num=input()
list=[int(i) for i in input().split()]
list=sorted(list)
set=set(list)
for i in list:
    if max(set)-min(set)>len(set):
        print('mistake')
        break
    if i+1 not in list:
        if i==list[-1] :
            if list[0]==1 :
                print(i+1)
                break
            print(str(list[0]-1)+" "+str(i+1))
            break
        print(i+1)
        break
发表于 2018-08-08 10:57:39 回复(0)
7t_头像 7t_
// Swift 4.0
let n = Int(readLine()!)!
let line = readLine()!

let list = (line.split(separator: " ").map { Int($0)! }).sorted { $0 < $1 }

var result = [Any]()

var allContinuous = true
for i in 0 ..< n-1 {
    let a = list[i+1] - list[i]
    if a == 1 {
        continue
    }
    else if a == 2 {
        if result.count == 0 {
            result.append(list[i]+1)
            allContinuous = false
        }
        else {
            result = ["mistake"]
            break
        }
    }
    else {
        result = ["mistake"]
        break
    }
}

if allContinuous && result.count == 0 {
    if list[0]-1 > 0 {
        result.append(list[0]-1)
    }
    result.append(list[n-1]+1)
}

for i in 0 ..< result.count {
    print(result[i], terminator: i == result.count-1 ? "\n" : " ")
}

发表于 2018-03-08 17:17:07 回复(0)
public class Main {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int n = sc.nextInt();
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
        }
        guess(numbers);
    }
    private static void guess(int[] numbers) {
        if (numbers.length == 0) {
            mistake();
        } else if (numbers.length == 1) {
            print(numbers[0] - 1, numbers[0] + 1);
        } else {
            int min = numbers[0], max = numbers[0], sum = numbers[0], first = numbers[0];
            boolean[] bitArr = new boolean[numbers.length * 2 + 1];
            bitArr[numbers.length] = true;
            for (int i = 1; i < numbers.length; i++) {
                sum += numbers[i];
                //以first为参照物,将数字对应位数置为true
                int index = numbers[i] - first;
                if ((index > 0 && index <= numbers.length) || (index < 0 && -index <= numbers.length)) {
                    bitArr[numbers.length - index] = true;
                } else if (index != 0) {//数字间距离过大,无法连续
                    mistake();
                    return;
                }
                if (numbers[i] > max) {
                    max = numbers[i];
                }
                if (numbers[i] < min) {
                    min = numbers[i];
                }
            }
            int actualCount = numbers.length;
            //求不重复数字个数
            int uniqueCount = 0;
            for (int i = 0; i < bitArr.length; i++) {
                if (bitArr[i]) {
                    uniqueCount++;
                }
            }
            if (actualCount != uniqueCount) {
                mistake();
                return;
            }
            //期望的数字个数
            int expectedCount = max - min + 1;
            //缺少的数字个数
            int lackCount = expectedCount - uniqueCount;
            if (lackCount == 0) {//数列连续
                print(min - 1, max + 1);
            } else if (lackCount == 1) {//中间缺少一个
                print(0, (max + min) * (numbers.length + 1) / 2 - sum);
            } else {//缺少多个
                mistake();
            }
        }
    }
    private static void mistake() {
        System.out.println("mistake");
    }
    private static void print(int i, int j) {
        if (i > 0) {
            System.out.println(i + " " + j);
        } else {
            System.out.println(j);
        }
    }
}
编辑于 2018-01-26 11:21:01 回复(0)
a = raw_input()
n = int(a)
b = raw_input()
c = b.split(' ')
num = map(int, c)

num = sorted(num)
ll = []
for i in range(n-1):
    if num[i]+1 != num[i+1]:
        ll.append(i)
        
if len(ll)==0:
    if num[0]==1:
        result = str(num[n-1]+1)
    else:
        result = str(num[0]-1)+' '+str(num[n-1]+1)
elif len(ll)==1:
    result = str(num[ll[0]]+1)
else:
    result = 'mistake'
print result 

发表于 2018-01-09 22:50:24 回复(0)
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm> 

using namespace std;

int main(){
    int n,m,count=0,mis=0;
    cin >> n;
    int num[50]={0};
    int res[50]={0};
    for(int i=0; i<n; i++){
        cin >> num[i];
        //cout <<num[i];
    }
    sort(num,num+n);
    for(int i=0; i<n-1; i++){
        if(num[i]+1 != num[i+1]){
            count++;
        }
    }
    
    if(count>1){
        cout << "mistake";
        return 0;
    }
    
    for(int i=0; i<n; i++){
        if(num[i]+2 == num[i+1]){
            cout << num[i] + 1;
            return 0;
        }else if(num[i]+2<num[i+1]){
            cout << "mistake";
        }
    }
    if(num[0]==1){
        cout << num[n-1]+1;
    }else{
        cout << num[0]-1 <<" "<< num[n-1]+1;
    }
    
    return 0;
    
}

发表于 2017-12-20 16:54:07 回复(0)
int main(int argc, const char * argv[]) {
    int n,i,j,temp=0,count=0;
    bool ismistake=false;
    cin>>n;
    int num[n],array[4]={0,0,0,0};
    for(i=0;i<n;i++){
        cin>>num[i];
    }
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(num[j]<num[i]){
                temp = num[i];
                num[i] = num[j];
                num[j] = temp;
            }
        }
    }
    for(i=0;i<n-1;i++){
        if((num[i+1]-num[i])>2){
            cout<<"mistake"<<endl;
            ismistake = true;
            break;
        }
        if(num[i+1]-num[i]==2){
            array[count] = num[i]+1;
            count ++;
        }
    }
    if(ismistake == false){
        if(count == 0){
            if(num[0]>1) cout<<num[0]-1<<" "<<num[n-1]+1;
            else cout<<num[n-1]+1;
        }
        else if(count>=2) cout<<"mistake"<<endl;
        else if(count == 1) cout<<array[0]<<endl;
    }
    return 0;
}


发表于 2017-11-06 20:29:12 回复(0)
import string
if __name__ == '__main__':
    input_size = string.atoi(raw_input())
    input_str = raw_input()
    input_int_list = [string.atoi(a) for a in input_str.split()]
    input_int_list.sort()
    
    if input_int_list[-1] - input_int_list[0] + 1 > input_size + 1:
        print 'mistake'
    if input_int_list[-1] - input_int_list[0] + 1 == input_size:
        if 1 != input_int_list[-1]:
            print str(input_int_list[0] - 1) + ' ' + str(input_int_list[-1] + 1)
            exit()
        print str(input_int_list[-1] + 1)
    for idx in range(len(input_int_list)-1):
        if input_int_list[idx] + 1 != input_int_list[idx+1]:
                     print str(input_int_list[idx] + 1)
        


您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为70.00%

测试用例:
3
1 3 5

对应输出应该为:

mistake

你的输出为:

mistake
编辑于 2017-11-02 15:52:36 回复(0)
def find_miss(nums):
    _min = float("+inf")
    _max = float("-inf")
    actual_total = 0
    for k in nums:
        flag = _max > _min
        if flag:
            if k > _max:
                _max = k
            elif k < _min:
                _min = k
        else:
            if k > _max:
                _max = k
            if k < _min:
                _min = k
        actual_total = actual_total + k
    predict_total = (_min + _max) * (_max - _min + 1)/2
    miss = predict_total - actual_total
    if miss == 0:
        print _min - 1, 'or', _max + 1
    elif miss > _max:
        print "mistake"
    else:
        print miss

if __name__ == '__main__':
    find_miss([5,6,7,8])
    find_miss([5,6,9,10])
    find_miss([5,6,8,9])


编辑于 2017-10-24 16:32:55 回复(0)