算法：7-1 数表问题

小颜同学

发布于 2023-08-24 08:21:21

1500

发布于 2023-08-24 08:21:21

文章被收录于专栏：原创笔记原创笔记

编个题面先：

小明是个爱学习的好孩子，上课的时候老师布置了这么一个作业题：

根据一张由N个正整数组成的数表，两两相加得到新数（共有N∗(N−1)/2个），然后将新数按照非递减排序。

举个例子呢就是：如果数表里包含有4个数1，4，3，9，那么正确答案就是4，5，7，10，12，13。

请你编程帮助小明完成这道题吧！

输入格式:

数据有两行，第1行是一个整数N（1<N≤100），表示数表中的整数个数；

第2行是数表中的N个整数（0≤整数≤5000），相邻整数间以一个空格分隔。

输入的N个整数确保不重复。

输出格式:

输出一组按照升序排列的整数的和，相邻整数之间以一个空格分隔。

输入样例:

在这里给出一组输入。例如：

4
1 4 3 9

输出样例:

在这里给出相应的输出。例如：

4 5 7 10 12 13

代码长度限制									   16 KB
时间限制										400 ms
内存限制										64 MB

代码演示:

刚开始未优化的方法：

import java.util.*;

public class  Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Scanner sc1 = new Scanner(System.in);
        String arr = sc1.nextLine();
        String arr1[] = arr.split(" ");
        int num[] = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(arr1[i]);
        }
		//Set无序集合可以自动去除重复的结果
        Set<Integer> list = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            for (int j = 0; j < num.length; j++) {
                if (num[i] != num[j]) {
                    list.add(num[i] + num[j]);
                }
            }
        }
        List<Integer> newList = new ArrayList<>();
        for (Integer arrInt:list) {
            newList.add(arrInt);
        }
        //对newList进行排序
        Collections.sort(newList);
        for (Integer newArr:newList) {
            System.out.print(newArr + " ");
        }
    }
}

运行结果：

满足条件正确解法：

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        sc.useDelimiter("\n");
        String ar =sc.next();
        String[] arArray = ar.split(" ");
        int a[]=new int[num];
        int i=0;
        for (String s : arArray) {
            int b= Integer.parseInt(s);
            a[i]=b;
            i++;
        }
        if (a.length==i){
            int b[] = new int[num*(num-1)/2];
            int l=0;
            for (int j = 0; j < num; j++) {
                for (int k = j+1; k < num; k++) {
                    b[l]=(a[j]+a[k]);
                    l++;
                }
            }
            for (int j = 0; j <b.length; j++) {
                for (int k = j+1; k < b.length; k++) {
                    if (b[j]>b[k]){
                        int e=b[j];
                        b[j]=b[k];
                        b[k]=e;
                    }
                }
            }
            for (int j = 0; j < b.length; j++) {
                System.out.print(b[j]);
                if (j<b.length-1){
                    System.out.print(" ");
                }
            }
        }
    }
}

运行结果：