Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1207466
  • 博文数量: 399
  • 博客积分: 8508
  • 博客等级: 中将
  • 技术积分: 5302
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-14 09:28
个人简介

能力强的人善于解决问题,有智慧的人善于绕过问题。 区别很微妙,小心谨慎做后者。

文章分类

全部博文(399)

文章存档

2018年(3)

2017年(1)

2016年(1)

2015年(69)

2013年(14)

2012年(17)

2011年(12)

2010年(189)

2009年(93)

分类: 架构设计与优化

2015-04-29 18:28:14

给定一个整数数组,返回它其中最长的连续整数数列长度。
例如 a[] = {100,4,200,1,3,2} 因为其中包含1,2,3,4所以返回4.

使用并查集算法实现,同时应用了路径压缩和秩的优化,你懂的。

package basic.datastructures;

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

public class UnionAndFind
{
  private final int[] internalData;

  public int[] getData()
  {
    return internalData;
  }

  class Node
  {
    Integer count;
    Integer root;

    Node( int count, int root )
    {
      this.count = count;
      this.root = root;
    }
  }

  private Map data;

  /**
   * At the beginning , every element itself is a set of family and then we unify
   *
   * @param n
   */
  void initialize( int n )
  {
    data.put( n, new Node( 1, n ) );
  }

  public UnionAndFind( final int[] x )
  {
    this.internalData = x;
    data = new HashMap<>();
  }

  int findRoot( int n )
  {
    if ( !data.containsKey( n ) )
    {
      return n;
    }
    if ( n == data.get( n ).root )
    {
      return n;
    }
    // Compress the path to improve performance
    return data.get( n ).root = findRoot( data.get( n ).root );
  }

  int unify( int n, int left, int right )
  {
    System.out.println( "Current=" + n + " , Letf=" + left + " , Right=" + right );

    if ( data.containsKey( left ) && data.containsKey( right )
         && !data.get( right ).root.equals( data.get( left ).root ) )
    {
      data.get( right ).root = left; // always choose the large tree as parent
      data.get( left ).count += data.get( right ).count + 1; // add the current element of index n
      data.get( n ).root = left;

      System.out.println( "Return count from merge " + data.get( left ).count );
      return data.get( left ).count;
    }

    if ( data.containsKey( left ) )
    {
      data.get( left ).count++;
      data.get( n ).root = left;

      System.out.println( "Return count from left " + data.get( left ).count );
      return data.get( left ).count;
    }

    if ( data.containsKey( right ) )
    {
      data.get( right ).count++;
      data.get( n ).root = right;
      System.out.println( "Return count from right " + data.get( right ).count );
      return data.get( right ).count;
    }
    System.out.println( "Return count 1" );
    return 1;
  }

  public static void main( String[] args )
  {
    final Map res = new HashMap<>();
    res.put( 1, 1 );
    UnionAndFind searcher = new UnionAndFind( new int[] { 100, 4, 200, 1, 3, 2 } );
    IntStream.range( 0, searcher.getData().length )
        .forEach( index -> {
                    searcher.initialize( searcher.getData()[ index ] );
                    res.put( 1,
                             Math.max( res.get( 1 ),
                                       searcher.unify( searcher.getData()[ index ],
                                                       searcher.findRoot( searcher.getData()[ index ] - 1 ),
                                                       searcher.findRoot( searcher.getData()[ index ] + 1 ) ) ) );
                  } );
    System.out.println( res.get( 1 ) );
  }
}



阅读(580) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~