首页 > 试题广场 > 有趣的数字
[编程题]有趣的数字
  • 热度指数:34454 时间限制: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
为什么上厕所会想到这种鬼问题。。。
发表于 2016-08-24 15:10:57 回复(27)
只想提个醒,在这儿被磕磕绊绊了好久,差最大值对数不用讲,已经讲得很明白,差最小值情况,在排完序后,一定要考虑到差值为零的情况,举个例子2,4,6,8最小差值对数是3(因为差值都是2),但是2,2,2,2这种情况,最小差值对数就不是三,而是6(3*4/2),希望注意
发表于 2016-08-28 17:23:43 回复(9)
第一遍没看懂题目,(智商余额不足了。。。)
看明白之后,感觉挺简单,直接O(n^2)就完了,但是好像O(n^2)超时。
改进后思路:
    1.先排序
         特殊情况:如果排完序之后发现数组中所有数都相同,直接输出结果
             结果为:差最大个数 = 差最小个数 = (n * (n-1))/2;(两两组合)
    2.统计数组中每种数字的个数(这里用的map)
    3.计算差最小个数
        3.1.如果数组中没有重复数字,说明最小差不为0,最小差肯定是数组中相邻两个数的差
            因此,遍历一边数组,计算并统计最小差。
        3.2.如果数组中有重复数字,说明最小差是0,此时,遍历一边map,数字个数不为0的
            数字会产生最小差0,利用公式计算即可
    4.计算差最大个数
        只有一种情况,最大值与最小值的两两组合,即最大值个数 * 最小值个数
    算法复杂度:排序O(nlogn), 统计O(n)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int[] a = new int[n];
			for(int i=0;i<n;i++){
				a[i] = sc.nextInt();
			}
			
			Arrays.sort(a);
			//如果数组中的值全相同,直接两两组合
			if(a[0] == a[n-1]){
				int tmp = (n*(n-1))/2;
				System.out.println(tmp + " " + tmp);
				continue;
			}
			//map用来统计
			Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
			for(int i=0;i<n;i++){
				if(map.containsKey(a[i]))
					map.put(a[i], map.get(a[i])+1);
				else
					map.put(a[i], 1);
			}
			//求差最小个数
			int minres = 0;
			if(map.size() == n){
				int min = Math.abs(a[1]-a[0]);
				for(int i=2;i<n;i++){
					int tmp = Math.abs(a[i]-a[i-1]);
					if(tmp == min)
						minres++;
					else if(tmp < min){
						min = tmp;
						minres = 1;
					}
				}
			}else{
				for(Integer key : map.keySet()){
					int val = map.get(key);
					if(val > 1){
						minres += (val * (val-1))/2;
					}
				}
			}
			//求差最大个数
			int maxres = 0;
			List<Integer> keyset = new ArrayList<Integer>(map.keySet());
			int val1 = map.get(keyset.get(0));
			int val2 = map.get(keyset.get(keyset.size()-1));
			maxres = val1 * val2;
			System.out.println(minres + " " + maxres);			
		}
	}

}


发表于 2016-08-14 23:07:11 回复(25)
经过两次修改,AC了,而且考虑了111元素全相同的情况,还要谢谢 lzdcqu 找到算法缺陷。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	while (cin >> n){
		if (n < 2){
			cout << 0 << ' ' << 0 << endl;
			continue;
		}
		if (n == 2){
			cout << 1 << ' ' << 1 << endl;
			continue;
		}
		//3个数以上的情况
		vector<int> data;
		while (n--){
			int temp;
			cin >> temp;
			data.push_back(temp);
		}
		int length = data.size();
		sort(data.begin(), data.end());
		//先求最小的,肯定是相邻的相减得到
		int min_val = abs(data[1] - data[0]);
		for (int i = 2; i < length; ++i){
			int cur = (data[i] - data[i - 1]);
			if (cur < min_val)
				min_val = cur;
		}
		//统计最小的数目
		int min_count = 0;
		if (min_val == 0){//有相同大小的数子,统计个数,用组合求对数
			for (int i = 1; i < length; ++i)
			{
				int j = i - 1;
				while (j >= 0 && data[i] == data[j]){
					++min_count;
					--j;
				}
			}
		}
		else
		{
			for (int i = 1; i < length; ++i){
				int cur = (data[i] - data[i - 1]);
				if (cur == min_val)
					++min_count;
			}
		}
		//求差最大的对数:最小的个数*最大的个数(如果最大的不等于最小的)
		int max_val = data[length - 1] - data[0];
		int max_count = 0;
		int a, b;
		a = b = 0;
		for (int i = 0; i < length; ++i){
			if (data[i] == data[0])
				++a;
		}
		for (int i = length - 1; i >= 0; --i){
			if (data[i] == data[length - 1])
				++b;
		}
		if (max_val == 0)//当最大等于最小,即数据全部一样eg. 1 1 1 1时,显然 4*4是不对的
			max_count = length*(length - 1) / 2;
		else
			max_count = a*b;

		cout << min_count << ' ' << max_count << endl;
	}
	return 0;
}

编辑于 2016-08-11 22:04:32 回复(11)
我觉得那些大公司在牛客笔试就是个坑,几个样例一起测,然后检查结果,如果输出结果稍有不对就GG,找bug可以找半天,结果发现输出的地方少了一个回车符,很尴尬
发表于 2016-08-04 14:57:26 回复(6)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void result(vector<int>&a, int n);
int main()
{
	int num;
	while (cin >> num)
	{
		int temp;
		vector<int>data;
		for (int i = 0; i < num; ++i)
		{
			cin >> temp;
			data.push_back(temp);
		}
		result(data, num);
	}
	return 0;
}

void result(vector<int>&a, int n)
{
	if (n > 1)
	{
		sort(a.begin(), a.end());
		int m1 = 1;
		int m2 = 1;
		for (int i = 0; i < n-1; ++i)
		{
			if (a[i + 1] != a[i])
				break;
			++m1;
		}
		for (int i = n - 1; i > 0; --i)
		{
			if (a[i - 1] != a[i])
				break;
			++m2;
		}
		int max = m1*m2;

		int min_temp = a[1] - a[0];
		int min = 0;
		for (int i = 2; i < n; ++i)
			if (a[i] - a[i - 1] < min_temp)
				min_temp = a[i] - a[i - 1];
		if (min_temp == 0)
		{
			for (int i = 1; i < n; ++i)
			{
				int j = i - 1;
				while (j >= 0 && a[j] == a[i])
				{
					++min;
					--j;
				}
			}
		}
		else
		{
			for (int i = 1; i < n; ++i)
				if (a[i] - a[i - 1] == min_temp)
					++min;
		}
		cout << min << ' ' << max << endl;
	}
}

发表于 2016-07-12 22:16:47 回复(10)
我的思路是先用快排,然后对有序数组分别求差值最大的对数和差值最小的对数。
快排之后,如果数组为常数数组,即最大值=最小值,则结果已经出来了。否则,进行下面的操作,其中:
1. 差值最大的好求,看有序数组有几个最小值和几个最大值,相乘即可。
2. 差值最小的,由于是有序数组,必定是相邻的差值较小,故由快排后的有序数组生成差值数组(即相邻的两两相减)。如果差值数组中0,则查看差值数组中连续0的组数,可以由排列组合知识计算总的差值最小的对数;如果差值数组中没有0,则只需计算差值数组中有多少个最小值即可。注:差值数组必定都是非负数。
3. 空间复杂度较大,需要一些辅助数组。
4. 时间复杂度:快排O(NlogN),求差值最大O(N),求差值最小O(N),所以最终的时间复杂度为O(NlogN)。
编辑于 2016-08-10 20:50:03 回复(2)

思路:

  1. 先排序
  2. 求差为最小值的对数 
    1. 先求最小值minVal
    2. 若存在重复的元素:差为0,双重循环求差为0的对数,即得到minCount
    3. 若不存在重复的元素:最小值只出现在相邻元素间,循环一次即可得到minCount
  3. 求差为最大值的对数 
    1. 若全部元素都相等,利用排列组合的知识:maxCount=x*(x-1)/2
    2. 若不是全部元素都相等:maxCount=最小元素的个数*最大元素的个数

注意:千万不要忽略重复元素的情况!比如:3 3 3 3,最大值对是6对!而不是3对,更不是12对!

所用数据结构: vector

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    int num,i,j;
    while(cin>>num)//读入元素的总个数
    {
        if(num<2)
        {
            cout<<0<<" "<<0<<endl;
            continue;
        }
        vector<int> arr;//arr不要声明为全局变量,不然全部测试数据都被存入了arr
        int length=num;
        int temp;
        while(num--)//不能写成while(cin>>temp),不然,全部测试数据都被一次性存入了arr
        {
            cin>>temp;
            arr.push_back(temp);
        }
        sort(arr.begin(),arr.end());//C++排序函数:对[begin,end)内所有元素排序

        //求最小值minVal
        int minVal=arr[1]-arr[0];
        for(i=1;i<length-1;++i)
        {
            int cur=arr[i+1]-arr[i];
            if(cur<minVal)
                minVal=cur;
        }
        //求最小值的个数minCount
        int minCount=0;
        if(minVal==0)//arr中有相等元素时
        {
            for(i=0;i<length-1;++i)
            {
                for(j=i+1;j<length;++j)
                {
                    if(arr[i]==arr[j])
                        ++minCount;
                }
            }
        }
        else//arr中无元素相等时
        {
            for(i=0;i<length-1;++i)
            {
                int cur=arr[i+1]-arr[i];
                if(cur==minVal)
                {
                    ++minCount;
                }
            }
        }

        //求最大值maxVal
        int maxVal=arr[length-1]-arr[0];
        //求最大值的个数maxCount
        int maxCount=0;
        if(maxVal==0)//全部元素都相等,利用组合原理
        {
            maxCount=length*(length-1)/2;
        }
        else//有不同的元素,最大值的个数=最小的个数*最大的个数
        {
            int smallCount=0,bigCount=0;
            for(i=0;i<length;++i)
            {
                if(arr[i]==arr[0])
                    ++smallCount;
                else if(arr[i]==arr[length-1])
                    ++bigCount;
            }
            maxCount=smallCount*bigCount;
        }
        cout<<minCount<<" "<<maxCount<<endl;
    }
    return 0;
}

发表于 2018-01-02 17:10:15 回复(1)
#include <iostream>
#include <map>
#include <utility>
using namespace std;
// 用一个map来存储输入的数,当存在相同的数时不插入新的数,而是将计数值+1
int main()
{
    int num;
    while(cin>>num)
    {
        map<int,int> myMap;
        bool flag = false;
        for(int i = 0; i < num ; i++)
        {
            int k ;
            cin>>k;
            map<int,int>::iterator ite;
            ite = myMap.find(k);
            if(ite != myMap.end())
            {    (*ite).second++;flag = true;}
            else
            {
                myMap.insert(make_pair(k,1));
            }
        } // end of for 读取输入的数据
         map<int,int>::iterator ite = myMap.begin();
        int min =0;
        int minv = -1;
        if(flag)  //如果存在相同的数
        {
             for( ; ite!= myMap.end(); ite++)
        	{
            	if((*ite).second > 1)
                    min += ((*ite).second * ((*ite).second -1 ))/2;
        	} //最小差元组对数等于所有相等的数构成的元组对
        }
        else
        {
           for( map<int,int>::iterator ite2 = (++myMap.begin()); (ite2)!= myMap.end(); ite2++,ite++ )
           {
                   int k = (*(ite2)).first - (*(ite)).first;
                    if( minv ==-1 || k < minv )
                        { min = (*ite).second * (*ite2).second ;
                                        minv = k; }
                    else if(minv == k)
                    {
                        min+= (*ite).second * (*ite2).second;
                    }
           }  // end of for 求不存在相等的值时的最小差的元组对数                             
        }// 最小对的个数
            int max;
        if( (*myMap.rbegin()).first != (*myMap.begin()).first)
              max = (*myMap.rbegin()).second * (*myMap.begin()).second;
        else
              max = (*myMap.rbegin()).second *((*myMap.rbegin()).second-1)/2;//最大差的对数
        cout<< min<<" "<<max<<endl;
       
    }
}

编辑于 2016-08-16 21:14:28 回复(9)
首先吐槽一下这个编译器,是真该好好查查漏洞了。明明正确的答案,非要说是错的,那我也是没办法了。已经将时间、空间复杂度降到最低了,代码如下(JS):

let shuru = [];
while(line = readline()){
    shuru.push(line);
}
shuru.forEach((item,index)=>{
    if(index % 2 != 0){
        shuru[index] = item.split(' ');
    }
})
function jisuan(arr){
    arr.sort((a,b)=>a-b);
    if(arr[0] == arr[arr.length - 1]){
        let count = (arr.length * (arr.length - 1)) / 2;
        console.log(count+ ' ' + count);
    }else{
        let minCount = 0,maxCount = 0;
        let min = 0,max = 0,minIndex = 0,maxIndex = arr.length - 1;
        while(arr[minIndex] == arr[0]){
            min++;
            minIndex++;
        }
        while(arr[maxIndex] == arr[arr.length - 1]){
            max++;
            maxIndex--;
        }
        maxCount = min * max;

        let newArr = [];
        arr.reduce((pre,now)=>{
            newArr.push(Math.abs(now - pre));
            return now;
        })
        let arr0 = [];
        let preIndex;
        newArr.forEach((item,index)=>{
            if(item == 0){
                if(newArr[index - 1] != 0){
                    preIndex = index;
                }
                if(newArr[index + 1] != 0){
                    arr0.push(index - preIndex + 1);
                }
            }
        })
        if(arr0.length != 0){
            arr0.forEach(e=>{
                minCount += (e * (e + 1)) / 2;
            })
        }
        
        if(minCount > 0){
            console.log(minCount + ' ' + maxCount);
        }else{
            newArr.sort((a,b)=>a-b);
            let minIndex2 = 0;
            while(newArr[minIndex2] == newArr[0]){
                minCount++;
                minIndex2++;
            }
            console.log(minCount + ' ' + maxCount);
        }
        
    }
}

shuru.forEach((item,index)=>{
    if(index % 2 != 0){
        item.forEach((item2,index2)=>{
            shuru[index][index2] = parseInt(item2);
        })
        jisuan(item);
    }
}) 

发表于 2019-04-22 17:35:13 回复(0)

python版本:

import sys 
def main():
    k = 0    
    for line in sys.stdin:   
        k = 1 - k        
        if (k == 0):            
            nums = [int(i) for i in line.strip().split()]            
            m = len(nums)            
            nums.sort()
            if nums[0] == nums[m-1]:
                n_max = n_min =  len(nums) * (len(nums) -1) / 2
                print n_min,n_max

            else:
                n_max = 0
                n_min = 0
                dict = {}
                for i in range(len(nums)):
                    if nums[i] in dict:
                        dict[nums[i]] = dict[nums[i]] + 1
                    else:
                        dict[nums[i]] = 1
                n_max = dict[nums[0]] * dict[nums[m-1]]

                if len(dict) != m:
                    for value in dict.values():
                        n_min = n_min + value * (value - 1) / 2
                else:
                    n_min = 1
                    l = []
                    for i in range(1,m):
                        l.append(nums[i] - nums[i-1])
                    l.sort()
                    i = 1
                    while l[i] == l[0]:
                        i +=1
                        n_min += 1

                print n_min,n_max
main()
发表于 2018-04-05 15:41:04 回复(2)
import java.util.Arrays;
import java.util.Scanner;

public class Jd_NumAbs {
	private static Scanner scanner = new Scanner(System.in);

	public static void main(String[] args) {
		while (scanner.hasNext()) {
			int num = scanner.nextInt();
			int[] nums = new int[num];
			for (int i = 0; i < num; i++) {
				nums[i] = scanner.nextInt();
			}
			// getMinMaxAbsNums(nums, num);
			fun2(nums, num);
		}
	}

	public static void getMinMaxAbsNums(int[] nums, int len) {
		int minNum = 0, maxNum = 0;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < len - 1; i++) {// 时间复杂度n^2
			for (int j = i + 1; j < len - 1; j++) {
				int abs = Math.abs(nums[i] - nums[j]);
				if (abs < min) {
					minNum = 1;
					min = abs;
				} else if (min == abs) {
					minNum++;
				} else if (abs > max) {
					max = abs;
					maxNum = 1;
				} else if (max == abs) {
					maxNum++;
				}
			}
		}
		System.out.println(minNum + " " + maxNum);
	}

	public static void fun2(int[] nums, int len) {
		Arrays.sort(nums);// 时间复杂度nlogn
		int maxCount = 0;
		int minNum = 1, maxNum = 1;// 数组中最小和最大元素的个数
		int i = 1;
		while (i < len && nums[i - 1] == nums[i]) {
			minNum++;
			i++;
		}
		i = len - 2;
		while (i >= 0 && nums[i] == nums[i + 1]) {
			maxNum++;
			i--;
		}
		if (nums[0] == nums[len - 1]) {
			maxCount = len * (len - 1) / 2;
		} else {
			maxCount = minNum * maxNum;
		}
		for (int j = 1; j < len; j++) {
			nums[j - 1] = Math.abs(nums[j] - nums[j - 1]);
		}
		int minValue = Integer.MAX_VALUE;
		int minCount = 0;
		for (int j = 0; j < nums.length; j++) {//初次统计minValue
			if (nums[j] < minValue) {
				minCount = 1;
				minValue=nums[j];
			} else if (nums[j] == minValue) {
				minCount++;
			}
		}
		if(minValue==0){//如果最小差值为0,统计0的区间个数
			minCount=0;
			int tempMinCount=0;
			for (int j = 0; j < len-1; j++) {
				if (nums[j]==0) {
					tempMinCount++;
				}else {
					minCount+=tempMinCount*(tempMinCount+1)/2;
					tempMinCount=0;
				}
			}
			minCount+=tempMinCount*(tempMinCount+1)/2;
		}
		System.out.println(minCount + " " + maxCount);
	}
}

发表于 2016-07-12 17:46:52 回复(2)
import sys
for line in sys.stdin:
    temp = [int(i) for i in line.split()]
    if len(temp) == 1:
        # 把N跳过
        continue
    temp.sort()
    Dict = {}
    for i in temp:
        if i in Dict:
            Dict[i] += 1
        else:
            Dict[i] = 1
    res = 0
    for k in Dict.keys():
        if Dict[k] >= 2:
            temp2 = [i for i in range(Dict[k])]
            res += sum(temp2)
    if res == 0: 
        # 没重复的情况,比如[1,2,3,9]这种
        temp3 = []
        for j in range(len(temp)-1):
            temp3.append(temp[j+1] - temp[j])
        temp3.sort()
        # print()会换行,算例通不过,加了end就不会换行
        print(temp3.count(temp3[0]), end=" ")
    else:
        print(res, end=" ")
    num_max, num_min = Dict[temp[-1]], Dict[temp[0]]
    print(num_max*num_min)
我用python3,各位一定要注意print()会直接换行,算例通不过
发表于 2021-04-01 21:23:28 回复(2)
 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 sys

def main():
	k = 0
	for line in sys.stdin:
		k = 1 - k
		if (k == 0):
			li = [int(i) for i in line.strip().split()]
			m = len(li)
			li.sort()
			
			small, big = li[0], li[m-1]
			smallnum, bignum, ansbig, anssmall, mincha, mincount = 1, 1, 0, 0, -1, 0
			
			# answer big
			while (li[smallnum] == small):
				smallnum += 1
			while (li[m-1-bignum] == big):
				bignum += 1
			ansbig = smallnum * bignum
			
			#answer small
			for i in range(m-1):
				if (li[i+1] - li[i] < mincha or mincha < 0):
					mincha = li[i+1] - li[i]
					mincount = 1
				elif (li[i+1] - li[i] == mincha):
					mincount += 1
			if (mincha > 0):
				anssmall = mincount
			else:
				p = 0
				for i in range(m-1):
					if (li[i+1] == li[i]):
						p += 1
					else:
						if (p > 0):
							anssmall += p * (p + 1) / 2
							p = 0
				anssmall += p * (p + 1) / 2
				
			print str(anssmall) + " " + str(ansbig)

main()

发表于 2017-03-26 16:16:20 回复(2)
思路:
先排序
最大差:最大值-最小值
最大差的对数:最大值的数量 * 最小值的数量

取两相邻数为一对,可使差值尽可能的小。
最小差:相邻的数中,差值最小的
最小差的对数:
1. 如果最小差为0,则为 每组相等数中 任选2个的所有 组合
2. 如果最小差不为0,则为 相邻数差值 = 最小差 的所有 数量
#include <stdio.h>
#include <algorithm>
int main() {
    int n, a[100000];
    while(~scanf("%d", &n)) {
        int t = n;
        while(t--) 
            scanf("%d", a + t);
        std::sort(a, a + n);
        int j = n - 2, nMin = 1, nMax = 1;
        int nMaxDiff = 0, nMinDiff = 0, minDiff = 0x7fffffff;
        while(nMin < n && a[nMin - 1] == a[nMin])
            nMin++;
        while(j >= 0 && a[j] == a[j + 1]) {
            j--;
            nMax++;
        }
        nMaxDiff = nMin * nMax;
        //find minDiff and add nMinDiff
        for(int i = 1; i < n; i++) {
            int d = a[i] - a[i - 1];
            if(d < minDiff) {
                minDiff = d;
                nMinDiff = 0;
            }
            if(minDiff == 0) 
                break;
            nMinDiff += (d == minDiff);
        }
        //minDiff = 0, find equal numbers and add nMinDiff
        if(minDiff == 0) {
            int m = 1;
            for(int i = 1; i < n; i++) {
                if(a[i] == a[i - 1]) {
                    m++;
                } else if(m > 1) {
                    nMinDiff += m * (m - 1)/2;
                    m = 1;
                }
            }
            nMinDiff += (m > 1) ? m * (m - 1)/2 : 0;
        }
        printf("%d %d\n", nMinDiff, nMaxDiff);
    }
    return 0;
}

编辑于 2017-01-05 14:41:32 回复(0)
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);
            int min=Integer.MAX_VALUE;
            int countmin=0;
            for(int i=1;i<n;i++){
                if(min>(num[i]-num[i-1])){
                    countmin=0;
                    min=num[i]-num[i-1];
                    if (min==0)
                    	break;
                    }
                 if((num[i]-num[i-1])==min)
                    countmin++;
            }
            if(min==0){
            	int min_num=1;
            	for(int i=1;i<n;i++){
            		if(num[i]==num[i-1]){
            			min_num++;
            		}
            		else if(min_num!=1){
            			countmin+=min_num*(min_num-1)/2;
            			min_num=1;
            		}
            	}
            }
             
            int countmax=0;
            int num1=0;
            int num2=0;
            int i=0;
            while(i<n){
                if(num[i]==num[0]){
                    num1++;
                i++;}
                else
                    break;
            }
            int j=n-1;
            while(j>=0){
                if(num[j]==num[n-1]){
                    num2++;
                    j--;}
                else
                    break;
            }
            countmax=num1*num2;
            System.out.println(countmin+" "+countmax);
             
        }
    }
}
测试用例只通过10%,最小对数有问题,而且是普通非相等情况出问题,不知怎么回事。

发表于 2016-09-26 17:45:37 回复(0)
1.先排序
         特殊情况:如果排完序之后发现数组中所有数都相同,直接输出结果
             结果为:差最大个数 = 差最小个数 = (n * (n-1))/2;(两两组合)
    2.统计数组中每种数字的个数(这里用的map)
    3.计算差最小个数
        3.1.如果数组中没有重复数字,说明最小差不为0,最小差肯定是数组中相邻两个数的差
            因此,遍历一边数组,计算并统计最小差。
        3.2.如果数组中有重复数字,说明最小差是0,此时,遍历一边map,数字个数不为0的
            数字会产生最小差0,利用公式计算即可
    4.计算差最大个数
        只有一种情况,最大值与最小值的两两组合,即最大值个数 * 最小值个数
发表于 2016-09-04 22:28:57 回复(1)
楼上高赞大佬说得很详细,遇到相等的数就使用组合数公式,否则计数自增1。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            int n = Integer.parseInt(line.trim());
            String[] strArr = br.readLine().trim().split(" ");
            int[] arr = new int[n];
            // 统计每个数的出现次数
            HashMap<Integer, Integer> counter = new HashMap<>();
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < n; i++){
                arr[i] = Integer.parseInt(strArr[i]);
                if(counter.containsKey(arr[i])){
                    counter.put(arr[i], counter.get(arr[i]) + 1);
                    min = 0;
                }else
                    counter.put(arr[i], 1);
            }
            Arrays.sort(arr);
            if(arr[n - 1] == arr[0]){
                // 最值相等,二元组数均为数组长度n的组合数
                System.out.println(n*(n - 1) / 2 + " " + n*(n - 1) / 2);
            }else{
                // 求最小差二元组数
                int minCount = 0;
                if(min == 0){
                    // 此时最小差值为0,二元组个数为每个重复数字出现次数的组合数之和
                    for(int num: counter.keySet())
                        if(counter.get(num) > 1) minCount += counter.get(num)*(counter.get(num) - 1) / 2;
                }else{
                    min = Math.abs(arr[1] - arr[0]);
                    for(int i = 2; i < n; i++){
                        int temp = Math.abs(arr[i] - arr[i - 1]);
                        if(temp == min)
                            minCount++;
                        else if(temp < min){
                            min = temp;
                            minCount = 1;
                        }
                    }
                }
                // 求最大差二元组数(最大和最小数组合,即最大数的个数*最小数的个数)
                int maxCount = counter.get(arr[0]) * counter.get(arr[n - 1]);
                System.out.println(minCount + " " + maxCount);
            }
        }
    }
}


发表于 2021-02-08 15:36:37 回复(0)
先使用sort排序,最大差值肯定是头尾数之差,最小值肯定出现在相邻数间
clude<iostream>
#include<vector>
(721)#include<algorithm>
using namespace std;
int main(){
    int n,t;
    while(cin>>n){
        vector<int> nums(n);
        for(int i=0;i<n;i++){
            cin>>nums[i];
        }
        sort(nums.begin(),nums.end());
        int mindis=nums[1]-nums[0];//初始值
        int maxdis=nums[n-1]-nums[0];//确定值
        int maxp=0,minp=0,tmp;
        for(int i=0;i<n-1;i++){
            mindis=min(nums[i+1]-nums[i],mindis);//找最小差值(出现在相邻数间)
        }
        for(int i=0;i<n;i++){
            for(int j=n-1;j>i;j--){
                tmp=nums[j]-nums[i];
                if(tmp==maxdis) maxp++;
                if(tmp==mindis) minp++;
            }
        }
        cout<<minp<<" " <<maxp<<endl;
    }
    return 0;
}


编辑于 2020-03-20 15:16:20 回复(1)

问题信息

难度:
223条回答 45939浏览

热门推荐

通过挑战的用户