How to tell if an a date occurs multiple times in an array/collection

Discussion in 'Java' started by laredotornado, Nov 18, 2009.

  1. Hi,

    I have an array of Calendar objects. How can I tell if any of the
    object's values in the array occurs more than once (e.g. two objects
    with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
    Calendar[] array to some other type of collection.

    Thanks, - Dave
     
    laredotornado, Nov 18, 2009
    #1
    1. Advertising

  2. laredotornado

    Lew Guest

    Re: How to tell if an a date occurs multiple times in anarray/collection

    laredotornado wrote:
    > I have an array of Calendar objects.  How can I tell if any of the
    > object's values in the array occurs more than once (e.g. two objects
    > with values "01-01-1999 9:00 AM")?  If it is easier, I can convert the
    > Calendar[] array to some other type of collection.
    >


    If you load the data into a 'Set <Calendar>' you cannot have any
    duplicates.

    Set <Calendar> calends =
    new HashSet <Calendar> ( Arrays.asList( getArrayOfCalendars() ));

    You can iterate over the array and load the counts into a
    'Map <Calendar, Integer>'.

    Map <Calendar, Integer> counts =
    new HashMap <Calendar, Integer>
    ( getArrayOfCalendars() .length * 4 / 3 );
    for ( Calendar calend : getArrayOfCalendars() )
    {
    Integer k = counts.get( calend );
    counts.put( calend, (k == null? 1 : k + 1) );
    }
    for ( Map.Entry <Calendar, Integer> entry : counts.entrySet() )
    {
    if ( entry.getValue() > 1 )
    {
    System.out.println( "Duplicates found for "+ entry.getKey() );
    }
    }

    This should be about O(n) for performance.

    --
    Lew
     
    Lew, Nov 18, 2009
    #2
    1. Advertising

  3. laredotornado

    Dagon Guest

    >laredotornado wrote:
    >> I have an array of Calendar objects. How can I tell if any of the
    >> object's values in the array occurs more than once (e.g. two objects
    >> with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
    >> Calendar[] array to some other type of collection.


    Heh, it's been a long time since I've seen this interview question. I have a
    secret hope that it's a real problem, but it seems unlikely.

    I'm going to assume that you care about millisecond precision, but do not care
    about what non-Date data (like timezone) the Calendar contains. Thus, I'll
    compare the getTimeInMillis() rather than just using .equals() or doing
    something more complicated to truncate to minutes as your example shows.

    Peter Duniho <> wrote:
    >The usual "most-efficient" approach would be to sort the data and then
    >look for consecutive duplicates.


    That's most efficient only if you don't want to allocate additional space.
    If you don't mind having a separate data structure, it's more efficient
    to build a hash as you check for duplicates.

    O(n) for a hash-based solution, O(n * logn) for the sort.

    >A less efficient alternative is to examine each element and search the
    >array for a duplicate. But that's O(n^2) instead of O(n log n). You'd
    >only want to do it that way if your collection is extremely small or for
    >some reason sorting (optionally copying before) the data was impossible.


    Build the search as you go. something like:

    Map<Long, Calendar> calendars = new HashMap<Long, Calendar>();
    for (Calendar c : calendarArray) {
    long calValue = c.getTimeInMillis();
    if (calendars.containsKey(calValue)) {
    // you have a duplicate! Do whatever you must!
    }
    calendars.put(calValue, c);
    }
    --
    Mark Rafn <http://www.dagon.net/>
     
    Dagon, Nov 19, 2009
    #3
  4. laredotornado

    Arne Vajhøj Guest

    laredotornado wrote:
    > I have an array of Calendar objects. How can I tell if any of the
    > object's values in the array occurs more than once (e.g. two objects
    > with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
    > Calendar[] array to some other type of collection.


    Set is probably the solution.

    But the implementation will depend a bit on what you consider same
    value.

    same second, timezone does not matter
    same millisecond, timezone does not matter
    same second, same timezone
    same millisecond, same timezone
    same second localtime
    same millisecond localtime

    Arne
     
    Arne Vajhøj, Nov 19, 2009
    #4
  5. laredotornado

    Roedy Green Guest

    On Wed, 18 Nov 2009 10:07:34 -0800 (PST), laredotornado
    <> wrote, quoted or indirectly quoted someone
    who said :

    >
    >I have an array of Calendar objects. How can I tell if any of the
    >object's values in the array occurs more than once (e.g. two objects
    >with values "01-01-1999 9:00 AM")? If it is easier, I can convert the
    >Calendar[] array to some other type of collection.


    An array is probably the most convenient and fast format.

    Just do a sort with Arrays.sort so the dups will be side by side.

    then scan down the array comparing current with prev marking dups as
    null.

    Track how many are left. Allocate an array that big and copy non-nulls
    into it.

    see http://mindprod.com/jgloss/sort.html
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    Finding a bug is a sign you were asleep a the switch when coding. Stop debugging, and go back over your code line by line.
     
    Roedy Green, Nov 19, 2009
    #5
  6. laredotornado

    Roedy Green Guest

    On Wed, 18 Nov 2009 10:31:19 -0800, Peter Duniho
    <> wrote, quoted or indirectly quoted
    someone who said :

    >The usual "most-efficient" approach would be to sort the data and then
    >look for consecutive duplicates.


    Another approach is to use a HashSet. Fill the set, it will
    automatically eliminate dups then extract the set as an array.
    The code for this is simpler, but I suspect it is slower.

    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    Finding a bug is a sign you were asleep a the switch when coding. Stop debugging, and go back over your code line by line.
     
    Roedy Green, Nov 19, 2009
    #6
  7. Re: How to tell if an a date occurs multiple times in anarray/collection

    Do this

    Set <Calendar> calends =
    new HashSet <Calendar> ( Arrays.asList( getArrayOfCalendars() ));

    You can iterate over the array and load the counts into a
    'Map <Calendar, Integer>'.

    Map <Calendar, Integer> counts =
    new HashMap <Calendar, Integer>
    ( getArrayOfCalendars() .length * 4 / 3 );
    for ( Calendar calend : getArrayOfCalendars() )
    {
    Integer k = counts.get( calend );
    counts.put( calend, (k == null? 1 : k + 1) );
    }
    for ( Map.Entry <Calendar, Integer> entry : counts.entrySet() )
    {
    if ( entry.getValue() > 1 )
    {
    System.out.println( "Duplicates found for "+ entry.getKey() );
    }
    }
     
    Teraposa Lunodas, Nov 24, 2009
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. mortb
    Replies:
    5
    Views:
    434
    Brock Allen
    Apr 8, 2005
  2. Øyvind Isaksen
    Replies:
    1
    Views:
    1,035
    Øyvind Isaksen
    May 18, 2007
  3. Jim Burgess
    Replies:
    11
    Views:
    401
    Jim Burgess
    Oct 9, 2009
  4. Thomas Greenwood
    Replies:
    7
    Views:
    183
    David Jacobs
    May 15, 2011
  5. libsfan01
    Replies:
    7
    Views:
    129
    Dr John Stockton
    Aug 13, 2006
Loading...

Share This Page