首页 > 试题广场 >

明明的随机数

[编程题]明明的随机数

热度指数：1618150 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于明明生成的 $n$ 个 $1$ 到 $500$ 之间的随机整数，你需要帮助他完成以下任务：
$\hspace{23pt}\bullet\,$ 删去重复的数字，即相同的数字只保留一个，把其余相同的数去掉；
$\hspace{23pt}\bullet\,$ 然后再把这些数从小到大排序，按照排好的顺序输出。
$\hspace{15pt}$ 你只需要输出最终的排序结果。

输入描述:

第一行输入一个整数 ，代表明明生成的数字个数。
此后  行，第  行输入一个整数 ，代表明明生成的随机整数。

输出描述:

输出若干行，每行输出一个整数，代表输入数据排序后的结果。第一行输出最小的数字。

示例1

输入

输出

1
2

算法知识视频讲解

wcz2023





#include <iostream>
using namespace std;
int main() {
	int N, n;
	while (cin >> N) {
        int a[1001] = { 0 };
		while (N--) {
			cin >> n;
			a[n] = 1;
		}
		for (int i = 0; i < 1001; i++)
			if (a[i])
				cout << i << endl;
	}
	return 0;
}

编辑于 2019-03-20 14:21:35 回复(351)

君莫笑swl

提供一个边输入边申请空间排序的解法

#include <stdio.h>

int cmp(int *a, int *b){
    return *a-*b;
}

int main(){
    int N = 0;
    //输入为空时结束
    while(~scanf("%d\n",&N)){
        int num = 0;
        //留出一个位置用于设置结束条件
        int *p = (int *)malloc(sizeof(int)*(N+1));
        //清空内存
        memset(p,0,sizeof(int)*(N+1));
        for(int i=0; i<N; i++){
            scanf("%d\n",&p[i]);
        }
        //快排函数运用,只排序前N个
        qsort(p,N,sizeof(int),cmp);
        int *t = p;
        //不清空内存就要在这设置 t[N] = '\0';
        //用while的坏处就是结尾后面如果连接别的数据就会继续循环
        while(*t != '\0'){
//             if(*t == num){
//                 *t++;
//                 continue;
//             }
//             else{
//                 num = *t++;
//                 printf("%d\n",num);                
//             }
            if(*t != *(t-1))
                printf("%d\n",*t);
            *t++;
        }
        free(p);
        t = NULL;
    }
    return 0;
}

发表于 2021-09-26 16:18:24 回复(0)

慵懒的网瘾少年

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    while(cin>>n)
    {
        vector<int> nums(n,0);
        for(int i = 0;i<n;i++)
        {
            cin>>nums[i];
        }
        sort(nums.begin(),nums.end());
        for(int i = 0;i<n;i++)
        {
            if(i>0&&nums[i]==nums[i-1]){continue;}
            cout<<nums[i]<<endl;
        }
    }
}

一个数组两次遍历，完事

发表于 2021-08-18 22:36:47 回复(0)

JavaScript

牛客242602195号

while(len = parseInt(readline(), 10)) {
    const buffer = Array(len).fill(0).map(() => parseInt(readline(), 10));
    console.log([...new Set(buffer.sort((a, b) => a - b))].join('\n'))
}

发表于 2021-03-28 22:33:55 回复(0)

C/C++

牛客132897473号

#include<iostream>

using namespace std;

int main()
{
    int data[1001] = {0};
    int n;
    int d;
    int max_index;
    while(cin>>n)
    {
        max_index = 0;
        while(n--)
        {
            cin >> d;
            data[d] = 1;
            max_index = d > max_index ? d : max_index;
        }
        
        for(int i=1;i <= max_index; i++)
        {
            if (data[i] == 1)
            {
                cout << i << '\n';
                data[i] = 0;
            }
        }
    }
}

编辑于 2021-01-30 02:41:42 回复(0)

JavaScript

牛客203793479号

// 自测没问题，保存并提交就出问题了，牛客你为什么这么烂！！！！
const listNum = [];
var data = '';
var size = 0;
while(data = readline()){
  if (size === 0) {
    size = data
  } else {
    size--;
    listNum.push(data);
  }
}

const sortList = listNum.sort((a, b) => a - b);

console.log(sortList
  .filter((item, index) => item !== sortList[index + 1])
  .join('\n'))
// 自测没问题，保存并提交就出问题了，牛客你为什么这么烂！！！！

编辑于 2021-01-19 21:49:03 回复(0)

C/C++

牛客121488550号

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
vector<int> vec;
while(1)
{
int count;
cin>>count;
if(cin.eof())
break;
while(count--)
{
int number;
cin>>number;
vec.push_back(number);
}
}
sort(vec.begin(),vec.end());
auto end_unique=unique(vec.begin(),vec.end());
vec.erase(end_unique,vec.end());
for(auto iter:vec)
cout<<iter<<endl;
return 0;
}

发表于 2021-01-15 14:59:46 回复(1)

牛客519176244号

import sys
while True:
line = sys.stdin.readline()
if not line:
break
t = set()
n = input()
for i in range(int(n)):
t.add(int(input()))

for i in sorted(t):

print(i)

# 这种也可以，但是不支持 import sys 爆粗

发表于 2020-11-02 14:36:58 回复(0)

牛客941361994号

绝大部分人都没有考虑输入容错的问题，当数字钟混入了字母，程序就会崩溃。

试试输入：3 1 a 2，你们的程序几乎全部崩溃或者死循环。

因此必须要检查scanf的有效性。

#include <stdio.h>

static const int MAX_NUM = 1001;

void srotArray(int* array,int num)
{
    int temp[MAX_NUM] = {0};
    int i;
    for(i=0;i<num;i++)
    {
        temp[array[i]] = 1;
    }
    for(i=0;i<MAX_NUM;i++)
    {
        if(temp[i]==1)
        printf("%d\n",i);
    }        
}

int main()
{
    int num = 0;
    int ch = 0;
    int ret = 0;
    int array[MAX_NUM] = {0};
    
    while(1)
    {
    	ret = scanf("%d",&num);
    	if(ret<=0)
        {
            break;//读取失败返回0,退出。
        }

        for(int i = 0;i<num;i++)
        {
        	array[i] = 0;
        }        
        
        for(int i = 0;i<num;i++)
        {
        	ret = scanf("%d",&ch);
        	if(ret<=0)          {
	            continue;//读取失败返回0,退出。
	        }
	        array[i] = ch;
        }
        srotArray(array,num);
    }
}

发表于 2020-10-10 10:38:01 回复(0)

牛客902931185号

var arr=[];
var start=0;
var num=0;
while(line=parseInt(readline())){
    if(start==0){
        num=line;
    }
    else if(start<=num)
    {
        arr.push(line); 
    }
    else{
        start=0;
        num=line;
    }
    start++;
}

arr.sort((a,b)=>{return a-b});
for(var i=0;i<arr.length;i++){
    if(i==0) console.log(arr[0]);
    else if(arr[i]==arr[i-1]) continue;
    else console.log(arr[i]);
}

（javascript v8 代码）题目有错误。输入跟实际输入不一致，导致我的代码一直运行不了。

编辑于 2020-08-28 21:59:00 回复(0)

Python

搅尽脑浆

插入排序一遍遍历，边遍历边去重

def insert_sort(arr):
    nums = set()
    dup_nums = 0
    i = 1
    nums.add(arr[0])
    while i < len(arr):
        key = arr[i]
        if key in nums:
            dup_nums = dup_nums + 1
            i = i + 1
            continue
        nums.add(key)
        j = i - 1 - dup_nums
        while j >= 0 and arr[j] > key:
             arr[j+1], arr[j] = arr[j], arr[j+1]
             j = j - 1
        arr[j+1], key = key, arr[j + 1]
        i = i + 1
    return arr[:len(arr)-dup_nums]

测试样例错误

[61,25,29,105,52,108,73,58,38,64,14,55,98,94,102,35,60,68,15,27,103,73,55,35,33,47,35,16,31,108,46,65,89,13,51,51,99,113,66,111,99,64,54,117,20,14,106,9,29,11,25,100,58,79,69,84,106,59,92,42,11,92]
排序去重之后少了第一个元素 61
以下是测试样例的结果：
[9, 11, 13, 14, 15, 16, 20, 25, 27, 29, 31, 33, 35, 38, 42, 46, 47, 51, 52, 54, 55, 58, 59, 60, 64, 65, 66, 68, 69, 73, 79, 84, 89, 92, 94, 98, 99, 100, 102, 103, 105, 106, 108, 111, 113, 117]
实际正确的结果：
[9, 11, 13, 14, 15, 16, 20, 25, 27, 29, 31, 33, 35, 38, 42, 46, 47, 51, 52, 54, 55, 58, 59, 60, 61, 64, 65, 66, 68, 69, 73, 79, 84, 89, 92, 94, 98, 99, 100, 102, 103, 105, 106, 108, 111, 113, 117]

编辑于 2020-07-23 09:43:19 回复(0)

上升期

噗,不知道怎么处理回车结束..结果对了,输出怎么错了..天,输入输出我都不熟练

#include<stdio.h>
#include<iostream>
#include<set>
using namespace std;
int main()
{
    std::set<int> eliminate_repeat;
    int num;
    while(std::cin>>num)
    {
        while(num--)
        {
            int value;
            std::cin >> value;
            eliminate_repeat.insert(value);
        }
        for(auto i:eliminate_repeat)
            std::cout << i << std::endl;
    }
    return 0;
}

发表于 2020-05-26 14:16:51 回复(0)

今天早睡今天早起

#include<stdio.h>

int main()
{
	int a[1001] = {0};
	int i = 0;
	int j;
	while (scanf("%d", &j) != EOF)
	{
		a[j] = j;
	}
	for (i = 0; i<1001; i++)
	{
		if (a[i] != 0)
			printf("%d\n", a[i]);
	}
    return 0;
}

很神奇，明明本地以及自测都能通过，最后提交出现问题，求打什么看看为什么

发表于 2020-05-07 15:52:15 回复(0)

牛客339600437号

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Set<Integer> set = new TreeSet<Integer>();
		while(scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] inputArray = new int[n];
			for(int i = 0;i < n;i ++) {
				inputArray[i] = scanner.nextInt();
				set.add(inputArray[i]);
			}
			for (Integer i : set) {
				System.out.println(i);
			}
			set.clear();
		}

		scanner.close();
	}
}

TreeSet即可解决去重加排序的目的

发表于 2020-03-31 20:39:54 回复(0)

susu1970

#include<iostream>
using namespace std;
short handle(short*arr,short start,short end){
  while(start<end){
    while(start<end&&arr[start]<=arr[end])--end;
    short tmp=arr[start];
    arr[start]=arr[end];
    arr[end]=tmp;
    while(start<end&&arr[start]<=arr[end])++start;
    tmp=arr[start];
    arr[start]=arr[end];
    arr[end]=tmp;    
  }
  return start;
}
void quick_sort(short *arr,short start,short end){
  if(start>=end)return;
  short tmp=handle(arr,start,end);
  quick_sort(arr,start,tmp-1);
  quick_sort(arr,tmp+1,end);
}
int main(){
  short n;
  while(cin>>n){
    short end=n-1,tmp;
    short arr[n];
    while(n>0&&cin>>tmp){
      arr[end+1-n]=tmp;
      --n;
    }
    quick_sort(arr,0,end);
    int i=0,j=1;
    cout<<arr[0]<<endl;
    for(;j<=end;++i,++j)
      if(arr[i]!=arr[j])cout<<arr[j]<<endl;
  }
}

发表于 2020-03-19 10:49:10 回复(0)

AsrielMao

这个题目描述让我很不舒服。

在“注”前面的input param和return value，让我读到这里的时候以为n和inputArray这两个东西是预输入的，类似C#里面Main(string[] args)这个args，然后那return value让我以为最后要return一个东西。但实际上都没有，所有东西都和前两题没什么差别，所有东西都是在main运行时再通过键盘输入。这五行字完全可以去掉，只需要看“注”后面的就很好明白了。

--------------

然后是解题。这个题目其实最大的难点还是“同一个测试用例里可能会有多组数据”。

例如两组数据，第一组为{10，20，30}，第二组为{60，50，40，70}。

那么输入就会是：

这里可能就会出现一个误区：“我们需要把这一堆一共9个数字全输入进去后输出结果”，但其实不是，我们完全可以在每输入完一组数据之后立刻输出结果，再输入下一组数据。这个考试验证结果，是将你所有的输出结果连在一起，与答案进行对比的。

第二个问题就是，我们不知道会输入多少组数据，如果输入示例是每行一组数据那就很明了了。但它是每行一个数据。于是我们就要用一个循环语句来输入数据，但循环什么时候停下来呢？从题目的输入示例里面我们无法直观地看出来（如果写题目的时候输入示例那里多空出一行，或者最后一行是个非数字、非正数等就明确多了），我们只能猜测，一般都是输入为空的时候结束。

发表于 2020-03-09 01:15:03 回复(0)

圣颖

看到一些同学的方法很巧妙，这里提供一个直接干的蠢办法：
先使用动态数组储存输入，然后快速排序，最后去重。

#include <iostream>
using namespace std;
int partition(int* inputArray,int lo, int hi) ;
 
void quicksort(int *inputArray,int lo, int hi) //快速排序 迭代形式
{
    if (hi - lo<2) return;
    int mi = partition(inputArray,lo, hi- 1);
    quicksort(inputArray,lo, mi);
    quicksort(inputArray,mi + 1, hi);
}
int partition(int* inputArray,int lo, int hi) {  //轴点构造算法
    int pivot = inputArray[lo];
    while (lo<hi) {
        while ((lo<hi) && (pivot <= inputArray[hi]))
            hi--;
        inputArray[lo] = inputArray[hi];
        while ((lo<hi) && (pivot>= inputArray[lo]))
            lo++;
        inputArray[hi] = inputArray[lo];
    }
    inputArray[lo] = pivot;
    return lo;
}
void remove(int *inputArray,int N){  //去重
    for(int i=1;i<N;i++)
        if (inputArray[i-1]==inputArray[i])
            inputArray[i-1]=0;
}
int main() {
    int N;
    while(cin>>N){
        int *inputArray=new int[N];
        for(int i=0;i<N;i++)
            cin>>inputArray[i];
        quicksort(inputArray,0,N);
        remove(inputArray,N);
        for(int i=0;i<N;i++)
            if(inputArray[i])
            cout<<inputArray[i]<<endl;
    }
}

发表于 2020-01-10 19:07:13 回复(0)

小陈也只是想要一个实习罢了

//再次感受到sort函数的厉害之处
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int* a=new int[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        cout<<a[0]<<endl;
        for(int i=1;i<n;i++)
            if(a[i]!=a[i-1])
                cout<<a[i]<<endl;
    }
    return 0;
}

发表于 2020-01-07 09:25:11 回复(0)

Alxemade

唯一注意的是这个需要考虑连续输入的，感觉OJ一定要考虑好输入输出的格式才行。

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

int main() {
    int N;
    while (cin >> N) {
        vector<int> array;
        int num;
        for (int i = 0; i < N; ++i) {
            cin >> num;
            array.push_back(num);
        }
        sort(array.begin(), array.end());
        vector<int>::iterator duplicated = unique(array.begin(), array.end());
        array.erase(duplicated, array.end());
        for (auto it : array) {
            cout << it << endl;
        }
    }
    return 0;
}

发表于 2019-08-16 20:06:26 回复(0)

C/C++

小红帽__

//此方法只能输入一行输出一行
/*#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    int num;
    vector<int> vec(1000,0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        vec[num]++;
    }
    for(int i=0;i<1000;++i)
    {
        if(vec[i]>0)
            cout<<i<<endl;
    }
    return 0;
}*/

#include <iostream>
#include<vector>
using namespace std;

int main()
{
    //输入多行 输出多行      //这个问题的表述本身有问题，它的测试数据不止有一组，很多朋友估计是因为这个原因一直没有通过   
   int n;//输入的随机数的个数
    int num;
   // vector<int> vec(1000,0);
    while(cin>>n)
    {
        vector<int> vec(1000,0);
        for(int i=0;i<n;++i)
        {
            cin>>num;
            vec[num]++;
        }
        for(int i=0;i<1000;++i)
        {
            if(vec[i]>0)
                cout<<i<<endl;
        }
    }
    return 0;
}

编辑于 2019-07-28 15:52:37 回复(0)