首页 > 编程语言 > 详细

在O(n)时间复杂度内求无序数组中任意两个元素的最大差值,以及存在的组数

时间:2017-12-06 23:40:45      阅读:134      评论:0      收藏:0      [点我收藏+]

标签:==   result   scan   span   pub   ger   oid   最小值   lose   

题目描述:

求无序数组中任意两个元素的最大差值,以及存在最大差值的组别数.

输入:

输入包含两行,第一行输入一个整数n;第二行n个正整数,用空格隔开.

输出:

输出为一行,包含最大差值,以及存在组别数.

样例输入:

4

4  1  2  1

输出:

3  2

一种实现代码如下(Java版):

 1 import java.util.Scanner;
 2 /**
 3  * 在O(n)时间复杂度内求无序数组中任意两个元素的最大差值,以及存在的组数
 4  * @author JiaJoa
 5  *
 6  */
 7 public class Main{
 8     public static void main(String args[]){
 9         Scanner cin = new Scanner(System.in);
10         int n = cin.nextInt();
11         int[] v = new int[n];
12         for(int i=0;i<n;i++){
13          v[i] = cin.nextInt();
14         }
15         getResult(n,v);
16         cin.close();
17     }
18         
19     public static void getResult(int n,int[] b){
20         int min = Integer.MAX_VALUE;  //记录最小值
21         int max = Integer.MIN_VALUE;  //记录最大值
22         int minCount = 0; //记录最小值的个数
23         int maxCount = 0; //记录最大值的个数
24         for(int i=0;i<n;i++){
25             if(b[i]==max){
26                 maxCount++;
27             }
28             if(b[i]>max){
29                 max = b[i];
30                 maxCount = 1;
31             }
32             
33             if(b[i]==min){
34                 minCount++;
35             }
36             if(b[i]<min){
37                 min = b[i];
38                 minCount = 1;
39             }
40         }
41         
42         int maxB = max - min;  //数组中两个数的最大差值
43         int count = maxCount*minCount;  //存在最大差值的组数
44         
45         System.out.println(maxB+" "+count);
46     }
47 }

 

在O(n)时间复杂度内求无序数组中任意两个元素的最大差值,以及存在的组数

标签:==   result   scan   span   pub   ger   oid   最小值   lose   

原文:http://www.cnblogs.com/JiaJoa/p/7994894.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号