[编程题]有趣的数字
- 热度指数：36005 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？
输入描述:
输入包含多组测试数据。
对于每组测试数据：
N - 本组测试数据有n个数
a1,a2...an - 需要计算的数据
保证:
1<=N<=100000,0<=ai<=INT_MAX.
输出描述:
对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
示例1
输入
6 45 12 45 32 5 6
输出
1 2
求解答，为什么输入之后会出现数组越界呢？
在eclipse上输入可以得出答案的😥😥
思路：
1.建立一个存差的数组c，c的长度是：（a的元素个数-1）*a的元素个数*0.5
2.对a的元素采取前一个减后一个并存入c中
3.将c按升序排列
4.统计与c[0]相等的元素个数-->最小值对数
5.统计与c[c.length-1]相等的元素个数-->最大值个数
import java.util.Scanner;
import java.util.Arrays;
public class eryuanshuzubijiaodaxiao {
import java.util.Arrays;
public class eryuanshuzubijiaodaxiao {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
//System.out.println("1");
int N=sc.nextInt();
//System.out.println();
//System.out.println("2");
//String[] a=sc.nextLine().split(" ");
int[] b=new int[N];
for(int i=0;i<b.length;i++) {
b[i]=sc.nextInt();
//b[i]=sc.nextInt()
}
sc.close();
int m=N*(N-1)/2;
int k=0;
int[] c=new int[m];
for(int i=0;i<N-1;i++) {
for(int j=i+1;j<N;j++) {
c[k++]=Math.abs(b[i]-b[j]);
}
}
System.out.println(k);
Arrays.sort(c);//对c从小到大排序
int p=1,q=1;
int x=c[0];
int y=c[c.length-1];
for(int i=1;i<c.length;i++) {
if(c[i]==x) p++;
else break;
}
for(int j=c.length-2;j>-1;j--) {
if(c[j]==y) q++;
else break;
}
System.out.println(p+" "+q);
//System.out.println();
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
//System.out.println("1");
int N=sc.nextInt();
//System.out.println();
//System.out.println("2");
//String[] a=sc.nextLine().split(" ");
int[] b=new int[N];
for(int i=0;i<b.length;i++) {
b[i]=sc.nextInt();
//b[i]=sc.nextInt()
}
sc.close();
int m=N*(N-1)/2;
int k=0;
int[] c=new int[m];
for(int i=0;i<N-1;i++) {
for(int j=i+1;j<N;j++) {
c[k++]=Math.abs(b[i]-b[j]);
}
}
System.out.println(k);
Arrays.sort(c);//对c从小到大排序
int p=1,q=1;
int x=c[0];
int y=c[c.length-1];
for(int i=1;i<c.length;i++) {
if(c[i]==x) p++;
else break;
}
for(int j=c.length-2;j>-1;j--) {
if(c[j]==y) q++;
else break;
}
System.out.println(p+" "+q);
//System.out.println();
}
}
发表于 2019-05-09 15:49:17
回复(0)
谁教教我，为什么超时
import java.util.Scanner;
public class Main{public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0 ;i<n;i++){
arr[i]=sc.nextInt();
}
int max = 0;
int min =Math.abs( arr[0]-arr[1] );
int maxcount=0,mincount=0;
for(int i = 0 ;i < n ; i++){
for(int j = i+1 ;j < n ; j++){
int temp =Math.abs(arr[i]-arr[j]);
if(temp>max){
max = temp;
maxcount = 1;
}
else if(temp== max){
maxcount++;
}
else if(temp<min){
min = temp;
mincount = 1;
}
else if(temp== min){
mincount++;
}
}
}
System.out.print(mincount+" "+maxcount);
}
}
发表于 2018-09-12 18:36:24
回复(0)
import java.util.*;
public class Main
{
public static void main(String []args)
{
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int sum = input.nextInt();
int a[] = new int[sum];
for(int i = 0;i < sum;i++)
{
a[i] = input.nextInt();
}
//排序
Arrays.sort(a);
//如果数组中数相同
if(a[0] == a[sum-1])
{
System.out.println((sum*(sum-1)/2)+" "+(sum*(sum-1)/2));
continue;
}
else{
/*
* 找最小差
* 因为数组已经从小到大排序。
* 所以最小差一定在数组相邻两数之间产生。
*/
int min = a[1] - a[0];//先默认a[1]-a[0]为最小值
for(int j = 1;j < a.length-1;j++)//循环比较相邻两数之差，找出最小差。
{
if((a[j+1] - a[j]) < min)
{
min = a[j+1] - a[j];
}
}
int minAmount = 0;
for(int k = 0;k < a.length -1;k++)//计数最小差个数
{
if((a[k+1] - a[k]) == min)
{
minAmount++;
}
}
/*
* 找最大
* 因为数组已经排好序
* 所以最大差必然是a[sum-1]-a[0]
* 最大差个数为最大值个数*最小值个数
*/
int maxA = 0;//最大值个数
int minA = 0;//最小值个数
int maxAmount = 0;
for(int m = 0;m < a.length;m++)
{
if(a[m] == a[0])
{
minA++;
}
if(a[m] == a[sum-1])
{
maxA++;
}
}
maxAmount = minA*maxA;
System.out.println(minAmount+" "+(maxA*minA));
}
}
}
}
发表于 2018-04-03 22:18:22
回复(1)
import java.util.*;
public class Main {
public static void main(String[] args) {
///输入处理
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = sc.nextInt();
}
//先对数组排序，方便找最大最小，也方便求每个数字的次数
Arrays.sort(num);
//如果所有的数字都相等，想想为什么要单独判断？
if (num[n - 1] == num[0]) {
int res = n * (n - 1) / 2;
System.out.println(res + " " + res);
continue; //continue返回，因为在while循环里面
//统计次数
}
//注意，此处用TreeMap，它能自动排序，因为后面
//求最大值时，需要用到
Map<Integer, Integer> map = new TreeMap<>();
for (int val : num) {
if (map.containsKey(val)) {
map.put(val, map.get(val) + 1);
} else {
map.put(val, 1);
}
}
//求最小值
int minCnt = 0;
if (map.size() == n) { //没有重复数字
int minNum = Math.abs(num[0] - num[1]);
for (int i = 1; i < n; i++) { //当需要数组中相邻的数字比较时，尤其注意数组越界的情况
int tmp = Math.abs(num[i] - num[i-1]);
if (tmp == minNum) {
minCnt ++;
} else if (tmp < minNum) {
minNum = tmp;
minCnt = 1;
}
}
} else {
for (int val : map.keySet()) {
int value = map.get(val);
if (value > 1) {
minCnt += (value * (value - 1)) / 2;
}
}
}
//求最大值
List<Integer> list = new ArrayList<>(map.keySet());
int max = map.get(list.get(0)) * map.get(list.get(list.size() - 1));
System.out.println(minCnt + " " + max);
}
}
}
发表于 2017-04-04 13:56:39
回复(0)
import java.util.*;
public class Main{
public static void main(String[] arg){
Scanner input = new Scanner(System.in);
int len;
while(input.hasNextInt()){
len = input.nextInt();
int[] a = new int[len];
for(int i = 0; i < len; i++)
a[i] = input.nextInt();
Arrays.sort(a);
//如果长度只有1 那么最大差和最小差都是这个数
if(len == 1) {
System.out.println(a[0]+" "+a[0]);
}
//如果差最小等于零 则找出有多少值相同的即可
//如果差最小不为零 则找相邻两个数的差是否等于最小值即可
//找出最小差
int min = Integer.MAX_VALUE;
for(int i = 0; i < len-1; i++){
if(a[i+1] - a[i] < min) min = a[i+1] - a[i];
if(min == 0) break; //最小差为零 不能再小了 退出
}
int min_counts = 0;
if(min == 0){
//最小差为零 统计一组值相等的个数 然后排列组合
//再统计下一组值相等得个数 排列组合 直到遍历完数组
int counts = 1;
int t = a[0];
for(int i = 1; i < len; i++){
if(a[i] == t) {
counts++;
}
else{
min_counts += Cn2(counts);
counts = 1;
t = a[i];
}
}
//循环退出了 else里还没执行 所以要补 怎么老是犯这种错误没补
min_counts += Cn2(counts);
}
else{
//最小差不为零 则只有相邻的两个数的差才可能等于最小差
for(int i = 0; i < len-1; i++){
if(a[i+1] - a[i] == min) min_counts++;
}
}
//差最大值就等于排序后的最后一个减去第一个
int max = a[len-1] - a[0];
int max_counts = 0;
//最大差为零 对数就等于所有值得排列组合
if(max == 0) max_counts = Cn2(len);
else{
//最大差不为零 对数就等于最大值的个数乘以最小值得个数
int counts_min = 0;
for(int i = 0; i < len; i++)
if(a[i] == a[0]) counts_min++;
int counts_max = 0;
for(int i = len-1; i >= 0; i--)
if(a[i] == a[len-1]) counts_max++;
max_counts = counts_max*counts_min;
}
System.out.println(min_counts+" "+max_counts);
}
}
//计算从n个数中取两个数的排列组合数
public static int Cn2(int n){
return n*(n-1)/2;
}
}
编辑于 2017-03-19 21:13:13
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i ++ ) {
arr[i] = sc.nextInt();
}
int res1 = 0, res2 = 0, minNum = 0, maxNum = 0, cha = Integer.MAX_VALUE;
Arrays.sort(arr);
if(arr[0] == arr[n - 1]) res1 = res2 = n * (n - 1) / 2;
else {
for (int i = 0; i < n; i ++ ) {
if(arr[i] == arr[0]) minNum ++ ;
if(arr[i] == arr[n - 1]) maxNum ++ ;
}
res2 = minNum * maxNum;
for (int i = 1; i < n; i ++ )
if(arr[i] - arr[i - 1] < cha) cha = arr[i] - arr[i - 1];
if(cha == 0) {
int temp = 1;
for (int i = 1; i < n; i ++ ) {
if(arr[i] == arr[i - 1]) temp ++ ;
else {
res1 += temp * (temp - 1) / 2;
temp = 1;
}
if(i == n - 1) res1 += temp * (temp - 1) / 2;
}
} else {
for (int i = 1; i < n; i ++ ) {
if(arr[i] - arr[i - 1] == cha) res1 ++ ;
}
}
}
System.out.println(res1 + " " + res2);
}
}
}
编辑于 2016-12-02 23:45:20
回复(0)
1. 排序（采用快排，直接插入排序也试过了，会超时）
2. 差最大的对数就是最小值的个数乘以最大数的个数
3. 差最小分两种情况。当数组中有相同元素时，最小值为0，则找出每个相同元素的个数，用等差数列求和的方式求出这个元素能组成的对数，然后将所有具有相同元素的对数和相加；当数组中没有相同元素，则想冒泡的方式一样一次找出最小的差值并累加对数。
import java.lang.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNextInt()) {
int n = scan.nextInt();
int arr[] = new int[n];
for(int i = 0;i < n;i++) {
arr[i] = scan.nextInt();
}
if(n == 1) {
System.out.println(0 + " " + 0);
return;
}
//快速排序
quickSort(arr,0,n-1);
int minNum = 1;
int maxNum = 1;
for(int i = 1;i < n-1; i++) {
if(arr[i] == arr[0]) {
minNum++;
}else {
break;
}
}
for(int i = n-2;i > 0; i--) {
if(arr[i] == arr[n-1]) {
maxNum++;
}else {
break;
}
}
//找最小的对数
//1.先看有没有相同的数字，有的话最小差值定是0，则找出所有相同值的个数，在用组合的方式计算
int num = 0;
int preNum = arr[0];
int sameNum = 1;
boolean hasSame = false;
for(int i = 1;i < n;i++) {
if(preNum == arr[i]) {
sameNum++;
}else {
if(sameNum > 1) {
hasSame = true;
//计算该值对应的对数
int subNum = (sameNum-1) * sameNum / 2;
num += subNum;
}
preNum = arr[i];
sameNum = 1;
}
}
if(!hasSame) {
int minDecline = Integer.MAX_VALUE;
for(int i = 0; i < n-1;i++) {
int decline = arr[i+1] - arr[i];
if(decline == minDecline) {
num++;
}else if(decline < minDecline) {
minDecline = decline;
num = 1;
}
}
}else {
if(sameNum > 1) {
num += (sameNum-1) * sameNum / 2;
}
}
System.out.println(num + " " + minNum * maxNum);
}
}
public static void quickSort(int[] arr,int low,int high) {
if(low < high) {
int partation = partation(arr,low,high);
quickSort(arr,low,partation-1);
quickSort(arr,partation+1,high);
}
}
public static int partation(int[] arr,int low,int high) {
int i = low - 1;
for(int j = low;j < high;j++) {
if(arr[j] < arr[high]) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
i++;
int tmp = arr[i];
arr[i] = arr[high];
arr[high] = tmp;
return i;
}
}
编辑于 2016-09-08 23:53:02
回复(0)
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
// 1、输入数组元素，并排序
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
Arrays.sort(nums);
// 2、寻找差的绝对值的最小值，同时统计最小值、最大值的个数
int c1 = 0;
int c2 = 1;
int min = Integer.MAX_VALUE;
HashMap<Integer, Integer> dif = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length - 1; i++) {
min = Math.min(min, nums[i + 1] - nums[i]);
if (nums[i] == nums[0])
c1++;
if (nums[i] == nums[nums.length - 1])
c2++;
if (dif.get(nums[i + 1] - nums[i]) != null) {
dif.put(nums[i + 1] - nums[i], dif.get(nums[i + 1] - nums[i]) + 1);
} else {
dif.put(nums[i + 1] - nums[i], 1);
}
}
// 3、计算差的绝对值最小的对数
int minCount = 0;
if (min == 0) { // 数组中有等值段
int label = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == label) {
count++;
} else {
label = nums[i];
minCount += (count * (count - 1)) / 2;
count = 1;
}
}
minCount += (count * (count - 1)) / 2;
} else { // 数组中没有等值段
minCount = dif.get(min);
}
// 4、计算差的绝对值最大的对数
int maxCount = 0;
if (nums[nums.length - 1] - nums[0] == 0) // 等值数组
maxCount = n * (n - 1) / 2;
else
maxCount = c1 * c2;
// 5、输出结果
System.out.println(minCount + " " + maxCount);
}
}
}
发表于 2016-07-21 14:49:42
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int minNum = 1;
int maxNum = 1;
int n = scanner.nextInt();
if(n==1){
int num = scanner.nextInt();
System.out.println("0 0");
}
if(n>1){
int[] num = new int[n];
for(int i = 0;i<n;i++){
num[i] = scanner.nextInt();
}
Arrays.sort(num);
int min = num[1]-num[0];
for(int i=1;i<n-1;i++){
int temp = num[i+1]-num[i];
if(min>temp){
min = temp;
minNum = 1;
}
else if(min==temp&min!=0){
minNum++;
}
}
//要考虑最小值为0
if(min==0){
minNum = 0;
int numTemp = num[0];
int numX = 1;
for(int i=1;i<n;i++){
if(num[i]==numTemp){
numX++;
}
else{
if(numX>1){
minNum=minNum+numX*(numX-1)/2;
}
numTemp=num[i];
numX=1;
}
}
//收尾忘了算导致十几分钟都在想
if(numX>1){
minNum=minNum+numX*(numX-1)/2;
}
}
int x=1;
int y=1;
//考虑最小值为0
if(num[0]==num[n-1]){
maxNum=n*(n-1)/2;
}
else{
for(int i=1;i<n;i++){
if(num[i]==num[0]){
x++;
}
else break;
}
for(int i=1;i<n-1;i++){
if(num[n-1-i]==num[n-1]){
y++;
}
else break;
}
maxNum = x*y;
}
System.out.println(minNum+" "+maxNum);
}
}
}
}
发表于 2016-07-19 13:11:49
回复(0)
import java.util.Scanner;
public class Main {
public int[] test(int[] a){
int min=Integer.MAX_VALUE;
int max=0;
int[] result=new int[2];
if(a.length>1){
for(int i=0;i<a.length-1;i++){
for(int j=i+1;j<a.length;j++){
if(Math.abs(a[j]-a[i])>max){
max=Math.abs(a[j]-a[i]);
result[1]=1;
}else if(Math.abs(a[j]-a[i])==max){
result[1]=result[1]+1;
}
if(Math.abs(a[j]-a[i])<min){
min=Math.abs(a[j]-a[i]);
result[0]=1;
}else if(Math.abs(a[j]-a[i])==min){
result[0]=result[0]+1;
}
}
}
}
return result;
}
public static void main(String[] args) {
Main s=new Main();
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int length=sc.nextInt();
int[] a=new int[length];
for(int i=0;i<length;i++){
a[i]=sc.nextInt();
}
int[] result=s.test(a);
System.out.println(result[0]+" "+result[1])；
} } } /*不懂为啥,总是提示运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。 自己怎么测试都没问题啊。。非法的输入也试了。。。求大神帮忙 */
发表于 2016-07-06 21:19:37
回复(0)
public static List<Integer> maxAndMin1(int num,List<Integer> list){
if (num<0||list==null||list.size()==0) {
return null;
}
Map<Integer, Integer> map = new TreeMap<>();
for(int i=0;i<num;i++){
if (map.containsKey(list.get(i))) {
map.put(list.get(i), map.get(list.get(i))+1);
}else {
map.put(list.get(i), 1);
}
}
boolean istrue = false;
int index = 0;
int min = Integer.MAX_VALUE;
Integer[]key =map.keySet().toArray(new Integer[1]);
for(int i=0;i<key.length;i++){
if (map.get(key[i])!=1) {
istrue = true;
int num2 = map.get(key[i]);
index += (num2*(num2-1))/2;
}
}
int minsize = 1;
if (istrue) {
minsize = index;
}else {
int min2 = Integer.MAX_VALUE;
for(int i=1;i<key.length;i++){
if (map.get(key[i])-map.get(key[i-1])<min2) {
min2 = map.get(key[i])-map.get(key[i-1]);
minsize = 1;
}else if (map.get(key[i])-map.get(key[i-1])==min2) {
minsize++;
}
}
}
int maxSize = map.get(key[key.length-1])*map.get(key[0]);
if (map.size()==1) {
maxSize = (map.get(key[0])*( map.get(key[0])-1))/2;
}
List<Integer> list2 = new ArrayList<>();
list2.add(minsize);
list2.add(maxSize);
return list2;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
int a=Integer.parseInt(scanner.nextLine());
String[] list = scanner.nextLine().split(" ");
List<Integer> list2 = new ArrayList<>();
for(String str:list){
list2.add(Integer.valueOf(str));
}
if (maxAndMin1(a,list2)!=null) {
System.out.println(maxAndMin1(a,list2).get(0)+" "+maxAndMin1(a,list2).get(1));
}
}
scanner.close();
} 实在不知道哪里有错
发表于 2016-06-16 18:17:46
回复(0)
问题信息
通过挑战的用户
-
2023-02-25 15:51:52
-
2022-11-17 00:02:22
-
2022-11-16 22:47:21 -
2022-11-10 23:13:02
-
2022-10-16 19:29:25
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
