计算两个数组相邻的成对出现个个数（咋个办呢 zgbn）

题目如下

有a1和a2都是为无符号数组，al1和al2为数组的长度，数组的长度为偶数。无符号数组有一对数字区间组成。

例如：a1={0,1,3,6,10,20,4,5}；

          a2={0,1,20,30,50,4,5}；

 其中：a1表示为下区间[0,1],[3,6],[10,20],[4,5]；

           a2标示为下区间[0,1],[20,30],[35,0],[4,5]；

则：计算a1和a2重叠的下区间个数。例如：a1和a2重叠下区间为[0,1][4,5]个数为2。

下面实现算法，计算1000000数组下区间重叠出现个数用时为90ms左右。

package com.demo;

import java.util.Random;

/**
 * 有a1和a2都是为无符号数组，al1和al2为数组的长度，数组的长度为偶数。
 * 无符号数组有一对数字区间组成，例如：
 * a1={0,1,3,6,10,20,4,5}
 * a2={0,1,20,30,50,4,5}
 * 则:
 *  a1表示为下区间[0,1],[3,6],[10,20],[4,5]
 *  a2标示为下区间[0,1],[20,30],[35,0],[4,5]
 * 计算a1和a2重叠的下区间个数。例如：a1和a2重叠下区间为[0,1][4,5]个数为2.

 * 下面实现算法，计算1000000数组下区间重叠出现个数用时为90ms左右。
 * 
 * @author ChenGang
 */
public class Demo01 {

 /**
  * @param args
  */
 public static void main(String[] args) {

  long time1 = System.currentTimeMillis() ;

  int num = 1000000 , len = 1000000 ;

  //声明数组 
  int[] num1 = randomArray(num,len) ;
  num1 = new int[]{0,1,3,6,10,20} ;
  System.out.println(String.format("生成数组num1用时：%dms",System.currentTimeMillis()-time1));

  int[] num2 = randomArray(num,len) ;
  num2 = new int[]{0,1,20,50,4,5} ;
  System.out.println(String.format("生成数组num2用时：%dms",System.currentTimeMillis()-time1));

  quickSort(num1);
  System.out.println(String.format("对数组num1排序用时：%dms",System.currentTimeMillis()-time1));

  quickSort(num2);
  System.out.println(String.format("对数组num2排序用时：%dms",System.currentTimeMillis()-time1));


  System.out.println(String.format("计算num1和num2重复出现成对数字个数 %d 。", excLogic(num1,num2)));
  System.out.println(String.format("计算num1和num2重复出现成对数字个数用时：%dms",System.currentTimeMillis()-time1));

 }

 /**
  * 计算下区间个数逻辑处理
  * @param _arr1
  * @param _arr2
  * @return
  */
 private static int excLogic(int[] _arr1 , int[] _arr2){

  int num = 0 ,  count=0 , idx1=0 , idx2=0 ;

  int[] arr1 = null , arr2 = null ;

  if(_arr1.length >= _arr2.length){
   arr1 = _arr1 ;
   arr2 = _arr2 ;
  }
  else{
   arr1 = _arr2 ;
   arr2 = _arr1 ;
  }

  while(idx1 < arr1.length){

   if(idx2>=arr2.length){
    break ;
   }

   if(arr1[idx1]==arr2[idx2]){
    count++ ;
    idx1++ ;
    idx2++ ;
   }
   else{
    if(count<2){
     idx1=idx1<=0?0:idx1-1 ;
     idx2=idx2+1 ;
    }
    else{
     if(idx1%2==0){
      idx2=idx2+2;
     }
     else{
      idx1=idx1<=0?0:idx1-1 ;
      idx2=idx2+1 ;
     }
     num = num+count/2 ;
    }
    count=0 ;
   }
  }

  if(count>0){
   num = count/2 ;
  }

  return num ;
 }

 /**
  * 构造随机数数组
  * @param num
  * @return
  */
 private static int[] randomArray(int num , int len){
  java.util.Random random = new Random() ;
  int[] arr = new int[len] ;
  for (int i = 0; i < arr.length; i++) {
   arr[i] = random.nextInt(num) ;
  }
  return arr ;
 }


 public static void quickSort(int[] a) {
  _quickSort(a,0,a.length-2) ;
 }

 /**
  * 对数组进行特殊化排序
  * @param arr
  * @return
  */
 private static void _quickSort(int[] a, int lo0, int hi0) { 

  int i = lo0 , j = hi0; 

  if (i >= j) 
   return; 
  //确定指针方向的逻辑变量 
  boolean flag=true; 

  while (i != j) { 
   if (a[i] > a[j] || (a[i]==a[j] && a[i+1]>a[j+1])) { 
    //交换数字 
    int temp1 = a[i];
    int temp2 = a[i+1];

    a[i] = a[j];
    a[i+1] = a[j+1];

    a[j] = temp1; 
    a[j+1] = temp2;

    flag = (flag == true) ? false : true; 
   } 
   //将指针向前或者向后移动 
   if(flag) 
    j=j-2; 
   else 
    i=i+2; 
  } 

  //将数组分开两半，确定每个数字的正确位置 
  i=i-2; 
  j=j+2; 
  _quickSort(a, lo0, i); 
  _quickSort(a, j, hi0); 

 } 

}

 

评论

1 楼 QuarterLifeForJava 2015-10-30  

其实我觉得你这道题，归到最后基本可以理解为两数组求并集