看花

[编程题]看花

热度指数：2713 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小明有一个花园，花园里面一共有m朵花，对于每一朵花，都是不一样的，小明用1～m中的一个整数表示每一朵花。

他很喜欢去看这些花，有一天他看了n次，并将n次他看花的种类是什么按照时间顺序记录下来。

记录用a[i]表示，表示第i次他看了a[i]这朵花。

小红很好奇，她有Q个问题,问[l,r]的时间内，小明一共看了多少朵不同的花儿，小明因为在忙着欣赏他的花儿，所以想请你帮他回答这些问题。

输入描述:

输入两个数n,m;(1<=n<=2000,1<=m<=100);分别表示n次看花，m表示一共有m朵花儿。

接下来输入n个数a[1]~a[n]，a[i]表示第i次，小明看的花的种类;

输入一个数Q(1<=Q<=1000000);表示小红的问题数量。

输入Q行 每行两个数l,r(1<=l<=r<=n);表示小红想知道在第l次到第r次，小明一共看了多少不同的花儿。

输出描述:

一共Q行

每一行输出一个数 表示小明在[l,r]的时间内看了多少种花。

示例1

输入

输出

3
2
3

算法知识视频讲解

Java

_000110hwc

通过率86%，运行超时，但是复杂度真没法再降了

java代码如下：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scn=new Scanner(System.in);
        while(scn.hasNextInt()){
            int n=scn.nextInt();
            int m=scn.nextInt();
            byte[] a=new byte[n];
            for(int i=0;i<n;i++) a[i]=scn.nextByte();
            int q=scn.nextInt();
            for(int i=0;i<q;i++){
                int l=scn.nextInt();
                int r=scn.nextInt();
                int t=0;
                byte[] c=new byte[m];
                for(int j=l-1;j<r;j++) c[a[j]-1]=1;
                for(byte cell:c) if(cell==1) t++;
                System.out.println(t);
            }
            break;
        }
    }
}

发表于 2020-06-30 21:57:03 回复(0)

Java

你瞅啥瞅

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int []A = new int [n];
        int []B = new int [m];
        for(int i=0;i<n;i++){
            A[i] = sc.nextInt();
        }
        int Q = sc.nextInt();
        int [][]a = new int [Q][2];
        for(int i=0;i<Q;i++){
            a[i][0] = sc.nextInt();
            a[i][1] = sc.nextInt();
        }
        
        
        for(int i=0;i<Q;i++){
        	int t=0;
        	for(int j=a[i][0]-1;j<=a[i][1]-1;j++){
        		int dd = A[j];
                if(B[dd-1]!=i+1){
                    B[dd-1]=i+1;
                    t++;
                }
        		
        	}
        	System.out.println(t);
        	
        	}
  
        }
    }

发表于 2019-08-16 16:02:59 回复(1)