题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

Input Param

n 输入随机数的个数

inputArray n个随机整数组成的数组

Return Value

OutputArray 输出处理后的随机整数

注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。

样例输入解释：

样例有两组测试
第一组是3个数字，分别是：2，2，1。
第二组是11个数字，分别是：10，20，40，32，67，40，20，89，300，400，15。

输入描述:
输入多行，先输入随机整数的个数，再输入相应个数的整数

输出描述:
返回多行，处理后的结果

示例1
输入

3
2
2
1
11
10
20
40
32
67
40
20
89
300
400
15

输出

1
2
10
15
20
32
40
67
89
300
400

解题思路

1 输入处理

题目案例存在多组case,所以采用循环的方式一直读取。同时将每一组的处理过程当成一个循环。

2 数组排序

数组排序可采用二分法排序。

3 去重

采用双指针方式处理。
初始指针 i, j 位置为 0
指针 j 先向右移动
比较指针 i,j 元素是否相同，若指针i，j元素相同则指针 j 继续向右移动；反之将指针 j 元素复制到指针 i + 1 处元素
当指针 j 移动到数组末尾时则停止

4 输出

#include <stdio.h>

void SortBinary(int num[],int count)
{
    int i,j;
    for (i=0; i<count; i++) {
        if (num[i] < num[i-1]) {
            int temp = num[i];
            int left = 0,right = i-1;
            while (left <= right) {
                int mid = (left +right)/2;
                if (num[mid] <temp) {
                    left = mid +1;
                }else
                {
                    right = mid -1;
                }
            }
            for (j = i; j >left; j--) {
                num[j] = num[j-1];
            }
            num[left] = temp;
        }
    }
}

int deduplite(int num[],int len)
{
    int i=0,j=1;

    while (j < len) {

        if (num[i] == num[j]) { // 指针 i, j 元素相同，说明重复元素。 j右移，i不动
             j++;
        }
        else if (i == j - 1) //指针 i, j 元素不相同，但i与j相邻，则i，j同时右移1
        {
            i++;
            j++;
        }
        else    //指针 i, j 元素不相同，且i与j不相邻
        {
            num[i+1] = num[j];
            i++;
            j++;
        }

    }
    return i+1;
}

int main()
{
// 1. 输入处理
    int i=0;
    int n=0;
    int inputArray[1000];

    while(scanf("%d",&n) != EOF)
    {
        for (i = 0; i<n; i++) {
            scanf("%d",&inputArray[i]);
        }
        //2. 排序
            SortBinary(inputArray, n);
        //3. 去重
            n = deduplite(inputArray, n);
        //4. 输出
            i = 0;
            while (i < n) {
                printf("%d\n",inputArray[i]);
                i++;
            }
    }

}