L2-017 人以群分 Java题解

2023-10-20 12:59
文章标签 java 题解 l2 017 人以群分

本文主要是介绍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代码,占用内存超出限制。

这篇关于L2-017 人以群分 Java题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/247256

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows