首页 > 试题广场 >

有趣的数字

[编程题]有趣的数字
  • 热度指数:35951 时间限制: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
我觉得那些大公司在牛客笔试就是个坑,几个样例一起测,然后检查结果,如果输出结果稍有不对就GG,找bug可以找半天,结果发现输出的地方少了一个回车符,很尴尬
发表于 2016-08-04 14:57:26 回复(6)
为什么上厕所会想到这种鬼问题。。。
发表于 2016-08-24 15:10:57 回复(27)
#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)
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)

C++ 哈希表(map) 实现

  • key存储元素值,value存储元素出现次数,map自动按照key升序排列
  • 注意题目所指的差值是 abs(x - y) ,一定是非负数,因此 (nums[i], nums[j])(nums[j],nums[i])是一种情况,即「组合数 」
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, x;
    while (cin >> n) {
        map<int, int> mp;   // 自动按照键排序
        while (n--) cin >> x, ++mp[x];
        int maxDiffCnt = 0, minDiffCnt = 0, minDiff = INT_MAX, pre = -1;

        if (mp.size() == 1) {    // map中只有一个元素的情况(个数为1 或 所有元素均相同)
            maxDiffCnt = mp.begin() -> second * (mp.begin() -> second - 1) / 2;
            printf("%d %d\n", maxDiffCnt, maxDiffCnt);
            continue;   // 本次遍历结束
        }

        // 以下为map中含有2个及以上元素的情况
        maxDiffCnt = mp.begin() -> second * prev(mp.end()) -> second;
        for (auto &[num, cnt] : mp) {
            if (cnt > 1) {  // 含有多个值相同的元素,则最大差值为0
                if (minDiff > 0) { minDiff = 0; minDiffCnt = 0; }
                minDiffCnt += cnt * (cnt - 1) / 2;  // 选择问题,cnt中选两个
            } else {    // 当前元素只有一个
                if (pre == -1);
                else if (num - pre == minDiff) {    // 差值与之前差值相同
                    ++minDiffCnt;
                } else if (num - pre < minDiff) {    // 差值比之前差值小,更新minDiff
                    minDiff = num - pre;
                    minDiffCnt = 1;
                }
            }
            pre = num;
        }
        printf("%d %d\n", minDiffCnt, maxDiffCnt);
    }
    return 0;
}
编辑于 2022-08-20 11:18:18 回复(0)
楼上高赞大佬说得很详细,遇到相等的数就使用组合数公式,否则计数自增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)
  1. //使用c++的map,“键-值”对,可以按键进行自动排序,首先使用一个map保存输入的数据  
  2. //“键”为输入的数据,“值”为该数据所出现的次数  
  3. //一共分三种情况:1、所有的输入数据都相同;2、有部分输入数据相同;3、所有的数据都不同   
  4. #include<iostream>  
  5. #include<vector>  
  6. #include<map>  
  7. #include<stdlib.h>  
  8. using namespace std;  
  9. int difference_min_num = 0;  
  10. void compare_fuc(map<int,int> mp1)  
  11. {  
  12.     map<int,int>::iterator iter;  
  13.     int max_num,min_num;  
  14.     max_num = (--mp1.end())->second;  
  15.     min_num = mp1.begin()->second;  
  16.     //所有的数据都相同,表示map只有一个数,差最小和差最大均为:min_num*(min_num-1)/2   
  17.     //差最大等于:最小值的个数×最大值的个数,下同   
  18.     if(mp1.size() == 1)  
  19.     {  
  20.         cout<<min_num*(min_num-1)/2<<" "<<min_num*(min_num-1)/2<<endl;  
  21.         return;  
  22.     }  
  23.     int tmp = 1;  
  24.     vector<int> vec,vec2;  
  25.     vec2.clear();  
  26.     vec.clear();  
  27.     for(map<int,int>::iterator j = mp1.begin();j != mp1.end();j++)  
  28.     {  
  29.         //将重复的数据的“值”放入vec   
  30.         if(j->second > 1)  
  31.             vec.push_back(j->second);  
  32.         vec2.push_back(j->first);  
  33.     }  
  34.     int sum_times = 0;  
  35.     //有部分相同的数据,差最小的总次数等于每个重复数据之和 ,而  
  36.     //每个重复数据的次数为: (*i)*(*i-1)/2  
  37.     if(vec.size() != 0)  
  38.     {  
  39.         for(vector<int>::iterator i = vec.begin();i != vec.end();i++)  
  40.             sum_times += (*i)*(*i-1)/2;  
  41.         cout<<sum_times<<" "<<max_num*min_num<<endl;  
  42.         return;  
  43.     }  
  44.     int tp = abs(vec2[1] - vec2[0]);  
  45.     difference_min_num = 0;  
  46.     //所有数据都不重复   
  47.     for(int j = 0;j != vec2.size()-1;j++)  
  48.     {  
  49.         if(abs(vec2[j] - vec2[j+1]) < tp)  
  50.         {  
  51.             tp = abs(vec2[j] - vec2[j+1]);  
  52.             difference_min_num = 1;  
  53.         }  
  54.         else if(abs(vec2[j] - vec2[j+1]) == tp)  
  55.             difference_min_num++;  
  56.     }  
  57.     cout<<difference_min_num<<" "<<max_num*min_num<<endl;  
  58. }  
  59. int main()  
  60. {  
  61.     int n,m;  
  62.     map<int,int> mp;  
  63.       
  64.     while(cin>>n)  
  65.     {  
  66.         mp.clear();  
  67.         for(int i = 0;i != n;i++)  
  68.         {  
  69.             cin>>m;  
  70.             mp[m]++;  
  71.         }  
  72.         compare_fuc(mp);  
  73.     }  
  74. }  
发表于 2019-11-14 16:14:10 回复(0)
import sys
 
def qSort(lst,start,end):
    """快速排序"""
    if start >= end:
        return
    i = start; j = end
    r = lst[i]    # 将lst[i]选做枢轴元素
    while i < j:
        while i < j and lst[j] >= r:
            j -= 1
        if i < j:
            lst[i] = lst[j]
            i += 1
        while  i < j and lst[i] <= r:
            i += 1
        if i < j:
            lst[j] = lst[i]
            j -= 1
    lst[i] = r
    qSort(lst,start,i-1)
    qSort(lst,i+1,end)

def getMaxPair(lst,n):
    # 数组中所有数字都相等,那么差最大的对就是它们两两组合
    if lst[0] == lst[n-1]:
        return n*(n-1)//2
    # 找出最小的数有多少个
    for i in range(1,n-1):
        if lst[i] != lst[0]:
            break
    # 找出最大的数有多少个
    for j in range(1,n-1):
        if lst[n-1-j] != lst[n-1]:
            break
    return i*j
 
def getMinPair(lst,n):
    # 数组中所有数字都相等,那么差最小的对就是它们两两组合
    if lst[0] == lst[n-1]:
        return n*(n-1)//2
    mincount = 0
    mindiff = lst[1] - lst[0]
    count = 1
    for i in range(1,n-1):
        # 差为0时对数的计算方法是不一样的,所以跳出
        if mindiff == 0:
            break
        if lst[i+1]-lst[i] == mindiff:
            count += 1
        elif lst[i+1]-lst[i] < mindiff:
            mindiff = lst[i+1]-lst[i]
            count = 1
    if mindiff == 0:
        for i in range(0,n-1):
            # 找出差为0的段的起始点
            if lst[i+1]-lst[i] == 0 and (i==0 or lst[i]-lst[i-1]>0):
                start = i
            # 找出差为0的段的终点
            if lst[i+1]-lst[i] == 0 and (i+1==n-1 or lst[i+2]-lst[i+1]>0):
                end = i+1
                equalnum = end-start+1
                # 可能存在多个差为0的子序列,故应分段计算,再把它们相加
                mincount = mincount + equalnum*(equalnum-1)//2
        return mincount
    else:
        return count

if __name__ == '__main__':
    while True:
        num = sys.stdin.readline().strip()
        if not num:
            break
        n = int(num)
        line = sys.stdin.readline().strip()
        if not line:
            break   # 这一步不能少,否则退出时会报错
        strlst = line.split(' ')
        lst = list(map(int,strlst))
        qSort(lst,0,n-1)
        print(str(getMinPair(lst,n))+' '+str(getMaxPair(lst,n)))

发表于 2019-10-10 17:49:14 回复(0)
import sys

def MaxAndMinPair(s):
    if len(s) <= 1:
        return 0
    s.sort(reverse=True)
    if s[0] == s[-1]:
        minPair = maxPair = int(len(s) * (len(s) - 1) / 2)
        print(str(minPair)+' '+str(maxPair))
    else:
        minGap = s[0] - s[-1]
        minPair = 1
        for i in range(len(s)-1):
            if s[i] - s[i + 1] < minGap:
                minGap = s[i] - s[i + 1]
                if minGap == 0:
                    break
                minPair = 1
                continue
            if s[i] - s[i + 1] == minGap:
                minPair += 1


        if minGap == 0:
            minPair = 0
            elementDic = {}
            for i in range(len(s)):
                if s[i] not in elementDic:
                    elementDic[s[i]] = 1
                else:
                    elementDic[s[i]] += 1
            for key in elementDic:
                num = elementDic[key]
                minPair += num*(num-1)/2

        # to find the max gap pair num
        # 2 1 1 1
        maxNum = 1
        minNum = 1
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                maxNum += 1
            else:
                break
        for i in range(len(s)-1):
            if s[len(s)-1-i] == s[len(s)-2-i]:
                minNum += 1
            else:
                break

        print(str(int(minPair)) + ' ' + str(maxNum * minNum))


if __name__ == '__main__':

    k = 0
    for line in sys.stdin:
        k = 1 - k
        if (k == 0):
            data = [int(i) for i in line.strip().split()]
            MaxAndMinPair(data)

python3版本:
    最大差对数:
        在对数组排序后,最大差值只能是产生于最大的数-最小的数,所以最大差对数=最大数个数*最小数个数
     最小差对数:
          情况1: 如果数组中有相等的数,那么最小差为0,所以统计可以产生差值为0的所有排列组合。对于其中一组相等的数来说,产生最小差对数 = C2/n = n*(n-1)/2(排列组合数学问题),累加所有组相等数可产生的最小差对数,就是整个数组可以产生最小差的对数。
           情况2:如果数组中没有相等的数,那么最小差就不为0,又因为数组是有序的,所以最小差只能产生于相邻两个数的作差,所以遍历一次数组即可求出对数
发表于 2019-09-14 11:11:27 回复(0)

贴一个排序后二分的代码,做的时候clang编译器有问题,给min_cha赋初值(long long)1e20最后一个测试数据会出错,本地g++就没问题,现在给min_cha赋值2*30就AC了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
ll A[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 0;
    while(cin >> n){
        for(int i=0;i<n;i++){
            cin >> A[i];
        }
        sort(A,A+n);
        ll min_cha = 1<<30;
        for(int i=1;i<n;i++){
            min_cha = min(min_cha,A[i]-A[i-1]);
        }
        ll ans1 = 0;
        for(int i=0;i<n-1;i++){
            int t = upper_bound(A,A+n,A[i]+min_cha)-A;
            ans1 += (t-i-1);
        }
        ll max_cha = A[n-1] - A[0];
        ll ans2 = 0;
        for(int i=0;i<n;i++){
            int t = lower_bound(A+i,A+n,A[i]+max_cha)-A;
            ans2 += (n-t);
        }
        cout << ans1 << " " << ans2 << endl;
    }

    return 0;
}
编辑于 2018-10-05 15:06:24 回复(0)

问题信息

难度:
227条回答 50869浏览

热门推荐

通过挑战的用户