Rumah  >  Artikel  >  Java  >  分享一个java计算的实例

分享一个java计算的实例

零下一度
零下一度asal
2017-07-21 17:25:261268semak imbas

n个数,求最小区间覆盖着n个数中所有的不相同的数字。

解题思路:

AC代码:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main{

	/**
	 * @param args
	 */
	static int n;
	static Set<Integer> set = new HashSet<Integer>() ; 
	static int a[]=new int[1000000+2];
	static Map<Integer,Integer> map=new HashMap<Integer, Integer>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan=new Scanner(System.in);
		n=scan.nextInt();
		for(int i = 0 ; i < n ; i++){  
            set.add(a[i] = scan.nextInt() ) ;  
        }  
		int  size = set.size() ;  //计算不同知识点的个数
		int start = 0 , end = 0 , sum = 0 ;  
        int res = n ; 
        for(;;){  
            while(end < n && sum < size){  
                Integer cnt = map.get(a[end]) ;  
                if(cnt == null){  
                    sum++ ;  
                    map.put(a[end] , 1) ;  
                }  
                else map.put(a[end] , cnt+1) ;  
                end++ ;  
            }  
            if(sum < size) break ;   
            res = Math.min(end - start , res) ;  
            int cnt = map.get(a[start]) ;   
            if(cnt == 1){  
                map.remove(a[start]) ;  
                sum-- ;  
            }  
            else map.put(a[start] , cnt-1) ;  
            start++ ;  
        }
        System.out.println(res) ;
	}

}

  

 

Atas ialah kandungan terperinci 分享一个java计算的实例. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn