首页 > 专题系列 > Java解POJ > POJ 3368 Frequent values [解题报告] Java
2013
11-12

POJ 3368 Frequent values [解题报告] Java

Frequent values

问题描述 :

You are given a sequence of n integers a1 , a2 , … , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , … , aj.

输入:

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , … , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, …, n}) separated by spaces. You can assume that for each i ∈ {1, …, n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the

query.

The last test case is followed by a line containing a single 0.

输出:

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

样例输入:

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

样例输出:

1
4
3

解题代码:

/* @author: [email protected]/
import java.io.*;
import java.util.*;
public class Main
{
  static  treex[] mytreex=new treex[210000];
  static int[] hash=new int[100005];
  static int[] left=new int[100005];
  static int[] right=new int[100005];
  static int[] data=new int[100005];
  static boolean build=false;
  static int k=0;
  
  public static void main(String args[]) throws Exception
  {
    InputStreamReader is=new InputStreamReader(System.in);
    BufferedReader in=new BufferedReader(is);
    String[] ss;
    StringBuffer res=new StringBuffer();
    while(true)
    {
    	build=false;
       ss=in.readLine().split(" ");
       int n=Integer.parseInt(ss[0]);
       if(n==0)
           break;
       int q=Integer.parseInt(ss[1]);
       ss=in.readLine().split(" ");
       k=1;
       for(int i=0;i< n;i++)
       {
           data[i]=Integer.parseInt(ss[i]);
           if(i>0&&data[i]!=data[i-1])
           {
           	right[k]=i-1;
           	left[k+1]=i;
              k++;
           }
           hash[i]=k;
         }
         right[k]=n-1;
         for(int i=0;i< q;i++)
         {
            ss=in.readLine().split(" ");
            int begin=Integer.parseInt(ss[0])-1;
            int end=Integer.parseInt(ss[1])-1;
            if(hash[begin]==hash[end])
            {
            	  res.append(end-begin+1);
            	  res.append("\n");
            	  continue;
            }
            if(hash[end]-hash[begin]==1)
            {
            	int l=right[hash[begin]]-begin+1;
            	int r=end-left[hash[end]]+1;
            	int temp=l>r?l:r;
            	res.append(temp);
            	res.append("\n");
            	continue;
            			
            }
            if(!build)
            {
            	  build=true;
            	  buildtreex(1,k,1);
            }
            int n1=right[hash[begin]]-begin+1;
            int n2=end-left[hash[end]]+1;
            if(n1< n2)
            	  n1=n2;
            n2=query(hash[begin]+1,hash[end]-1,1);
            res.append(n1>n2?n1:n2);
            res.append("\n");    

        }
      }
      System.out.print(res.toString());
   }
            
  public static void buildtreex(int a,int b,int i)
  {
      if(mytreex[i]==null)
            mytreex[i]=new treex();
      mytreex[i].left=a;
      mytreex[i].right=b;
      if(a==b)
           mytreex[i].max=right[a]-left[a]+1;
      if(a!=b)
      {
           int mid=(a+b)/2;
           buildtreex(a,mid,i*2);
           buildtreex(mid+1,b,i*2+1);
           mytreex[i].max=mytreex[i*2].max>mytreex[i*2+1].max?mytreex[i*2].max:mytreex[i*2+1].max;
      }
   }
            
            
  public static int query(int a,int b,int i)
  {
     if(a==mytreex[i].left&&b==mytreex[i].right)
          return mytreex[i].max;
     int mid=(mytreex[i].left+mytreex[i].right)/2;
     if(b<=mid)
        return query(a,b,2*i);
     else if(a>=mid+1)
        return query(a,b,2*i+1);
     else
     {
       int l =query(a,mid,2*i);
       int r = query(mid+1,b,2*i+1);
       return l>r?l:r;
     }
  }
            
}

class treex
{
	int left;
	int right;
	int max;
}

  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了