L2-017 人以群分 Java题解

原题：

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。

输入格式：

输入第一行给出一个正整数N（2≤N≤105）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过231。

输出格式：

按下列格式输出：

Outgoing #: N1
Introverted #: N2
Diff = N3

其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。

输入样例1：

10
23 8 10 99 46 2333 46 1 666 555

输出样例1：

Outgoing #: 5
Introverted #: 5
Diff = 3611

输入样例2：

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出样例2：

Outgoing #: 7
Introverted #: 6
Diff = 9359

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

题目详情 - L2-017 人以群分 (pintia.cn)https://pintia.cn/problem-sets/994805046380707840/problems/994805061056577536

题解：

只需通过对数组进行排序，得到一个递增的数组，此时数组的前一半每个元素都小于该数组的后一半，不难发现，此时两边的差异达到最大。

通过C++代码运行较为容易，耗时短，内存占用少，但由于最近学习Java，所以尝试通过Java解答本题。C++代码对照在Java代码下方。

在初次运行时，使用Scanner输入流，导致测试样例全部超时，于是尝试用BufferedReader字符流输入，减少了50ms以上的耗时，但仍然有两个测试样例没能通过。

虽然超时，但是占用空间仍然没有达到系统限制，因此我尝试使用相较于Java提供的的sort（Dual-Pivot快排）以及parallelSort排序（并行排序-合并排序）而言（时间复杂度均为O（nlogn）），时间复杂度更低的桶排序（时间复杂度为O（n+m）），但就结果而言，由于Java语言特性，难以使用Java语言通过全部测试用例，使用桶排序会造成内存超出64MB的限制，因此最终还是使用Collections下的sort排序。

Java代码如下：

使用Collections下的sort方法，由于超时，代码未能通过全部测试点：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;public class Main {private final int Num;        //人数private final ArrayList<Integer> People = new ArrayList<>();   //存放每个人的性格private int count;      //性格总计public Main() throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));Num = Integer.parseInt(reader.readLine());String[] ss = reader.readLine().split(" ");for (int i = 0; i < Num; i++) {People.add(Integer.parseInt(ss[i]));count += People.get(i);}Collections.sort(People);}public static void main(String[] args) throws IOException {Main main = new Main();for (int i = 0; i < main.Num / 2; i++)main.count -= 2 * main.People.get(i);System.out.println("Outgoing #: " + (main.Num / 2 + main.Num % 2));System.out.println("Introverted #: " + main.Num / 2);System.out.println("Diff = " + main.count);}
}

C++代码如下：

可以看出，C++代码在运行时，占用内存更小，耗时更短。

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int num;int diff;cin >> num;int people[num];for (int i = 0; i < num; i++){cin >> people[i];diff += people[i];}sort(people, people + num);for (int i = 0; i < num / 2; i++)diff -= 2 * people[i];cout << "Outgoing #: " << (num + 1) / 2 << endl;cout << "Introverted #: " << num / 2 << endl;cout << "Diff = " << diff << endl;system("pause");return 0;
}

使用桶排序的Java代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;public class Main {private int Num;        //人数private ArrayList<Integer> People = new ArrayList<>();   //存放每个人的性格private int count;      //性格总计private int Max;    //数组最大值private int Min;    //数组最小值public Main() throws IOException {BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));Max = Integer.MIN_VALUE;Min = Integer.MAX_VALUE;count = 0;Num = Integer.parseInt(reader.readLine());String[] s = reader.readLine().split(" ");for (int i = 0; i < Num; i++) {People.add(Integer.parseInt(s[i]));Max = Math.max(Max, (Integer) People.get(i));Min = Math.min(Min, (Integer) People.get(i));count += (int) People.get(i);}
//        Collections.sort(People);}public static void main(String[] args) throws IOException {Main split = new Main();split.BucketSort();for (int i = 0; i < split.Num / 2; i++)split.count -= 2 * split.People.get(i);System.out.println("Outgoing #: " + (split.Num / 2 + split.Num % 2));System.out.println("Introverted #: " + split.Num / 2);System.out.println("Diff = " + split.count);}public void BucketSort() {
//       桶数int bucketNum = (Max - Min) / Num + 1;ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);for (int i = 0; i < bucketNum; i++) {bucketArr.add(new ArrayList<>());}
//        置入桶中for (int i = 0; i < Num; i++) {int num = (People.get(i) - Min) / (Num);bucketArr.get(num).add(People.get(i));}
//        桶排序for (ArrayList<Integer> integers : bucketArr) {Collections.sort(integers);}
//        返回People.clear();for (ArrayList<Integer> integers : bucketArr) {People.addAll(integers);}}
}

分析：

Java程序编译后产生.class文件运行在JVM上，占用相当大的时间以及内存，在Windows上这种感知尤为明显。

关于桶排序：

详解：https://www.cnblogs.com/bigsaltfish/p/10067011.html

N:待排序长度         M:桶的数量

时间复杂度：O ( N + N * ( logN-logM ) )

空间复杂度：O ( N + M )

桶排序是一种牺牲空间换取时间的排序算法，当分配的桶的数量达到N时，时间复杂度最好，为O ( N  )，但空间复杂度上升，如果N较大，则会占用非常大的内存空间，如上方使用桶排序的Java代码，占用内存超出限制。