Return to Answer

fix for leading zeroes, as pointed out by @RobAu

Source Link

edited Oct 30, 2017 at 15:42

2.8k
12
25

import java.util.*;

public class Main {
  public static void main(String[] args) {
    final Scanner in = new Scanner(System.in);
    int count = in.nextInt();
    
    /* We split duplicate detection in an unsorted part that just saves whether
     * we've seen it before, and a sorted part that stores actual duplicates in
     * lexicographical order. */
    final Set<Integer> seen = new HashSet<>();
    final NavigableMap<Integer, Integer> duplicates = new TreeMap<>();
    
    while ( count-- > 0 ) {
      String strnum = in.next();
      final Integer number = parse(strnum);
      
      if ( !seen.add(number) ) {
        // number of dupes is number of encounters minus one
        duplicates.merge(number, 1, Integer::sum);
      }
    }
    
    if ( duplicates.isEmpty() ) {
      System.out.println("No duplicates.");
    } else {
      for ( Map.Entry<Integer, Integer> duplicate : duplicates.entrySet() ) {
        // don't forget to add one to the dupe count to get total count
        System.out.println(format(duplicate.getKey()) + " " + (duplicate.getValue() + 1));
      }
    }
  }
  
  /** Formats a parsed phone number to its normal form (NNN-NNNN). */
  static String format(int phoneNumber) {
    returnfinal (int prefix = phoneNumber / 10000)10000;
 + "-" + (final int suffix = phoneNumber % 1000010000;
    return String.format("%03d-%04d", prefix, suffix);
  }
  
  /** Parses an unformatted phone number string, considering only the alphanumerics.
    * Does not guard for overflow. */
  static int parse(String number) {
    int retval = 0;
    for ( int i = 0; i < number.length(); i++ ) {
      int digit;
      final char c = number.charAt(i);
      switch ( c ) {
        case '0':
          digit = 0;
          break;
        
        case '1':
          digit = 1;
          break;
      
        case '2': case 'A': case 'B': case 'C':
          digit = 2;
          break;
          
        case '3': case 'D': case 'E': case 'F':
          digit = 3;
          break;
          
        case '4': case 'G': case 'H': case 'I':
          digit = 4;
          break;
          
        case '5': case 'J': case 'K': case 'L':
          digit = 5;
          break;
          
        case '6': case 'M': case 'N': case 'O':
          digit = 6;
          break;
          
        case '7': case 'P': case 'R': case 'S':
          digit = 7;
          break;
          
        case '8': case 'T': case 'U': case 'V':
          digit = 8;
          break;
          
        case '9': case 'W': case 'X': case 'Y':
          digit = 9;
          break;
          
        default:
          continue;
      }
      
      retval = 10 * retval + digit;
    }
    
    return retval;
  }
}

import java.util.*;

public class Main {
  public static void main(String[] args) {
    final Scanner in = new Scanner(System.in);
    int count = in.nextInt();
    
    /* We split duplicate detection in an unsorted part that just saves whether
     * we've seen it before, and a sorted part that stores actual duplicates in
     * lexicographical order. */
    final Set<Integer> seen = new HashSet<>();
    final NavigableMap<Integer, Integer> duplicates = new TreeMap<>();
    
    while ( count-- > 0 ) {
      String strnum = in.next();
      final Integer number = parse(strnum);
      
      if ( !seen.add(number) ) {
        // number of dupes is number of encounters minus one
        duplicates.merge(number, 1, Integer::sum);
      }
    }
    
    if ( duplicates.isEmpty() ) {
      System.out.println("No duplicates.");
    } else {
      for ( Map.Entry<Integer, Integer> duplicate : duplicates.entrySet() ) {
        // don't forget to add one to the dupe count to get total count
        System.out.println(format(duplicate.getKey()) + " " + (duplicate.getValue() + 1));
      }
    }
  }
  
  /** Formats a parsed phone number to its normal form (NNN-NNNN). */
  static String format(int phoneNumber) {
    return (phoneNumber / 10000) + "-" + (phoneNumber % 10000);
  }
  
  /** Parses an unformatted phone number string, considering only the alphanumerics.
    * Does not guard for overflow. */
  static int parse(String number) {
    int retval = 0;
    for ( int i = 0; i < number.length(); i++ ) {
      int digit;
      final char c = number.charAt(i);
      switch ( c ) {
        case '0':
          digit = 0;
          break;
        
        case '1':
          digit = 1;
          break;
      
        case '2': case 'A': case 'B': case 'C':
          digit = 2;
          break;
          
        case '3': case 'D': case 'E': case 'F':
          digit = 3;
          break;
          
        case '4': case 'G': case 'H': case 'I':
          digit = 4;
          break;
          
        case '5': case 'J': case 'K': case 'L':
          digit = 5;
          break;
          
        case '6': case 'M': case 'N': case 'O':
          digit = 6;
          break;
          
        case '7': case 'P': case 'R': case 'S':
          digit = 7;
          break;
          
        case '8': case 'T': case 'U': case 'V':
          digit = 8;
          break;
          
        case '9': case 'W': case 'X': case 'Y':
          digit = 9;
          break;
          
        default:
          continue;
      }
      
      retval = 10 * retval + digit;
    }
    
    return retval;
  }
}

import java.util.*;

public class Main {
  public static void main(String[] args) {
    final Scanner in = new Scanner(System.in);
    int count = in.nextInt();
    
    /* We split duplicate detection in an unsorted part that just saves whether
     * we've seen it before, and a sorted part that stores actual duplicates in
     * lexicographical order. */
    final Set<Integer> seen = new HashSet<>();
    final NavigableMap<Integer, Integer> duplicates = new TreeMap<>();
    
    while ( count-- > 0 ) {
      String strnum = in.next();
      final Integer number = parse(strnum);
      
      if ( !seen.add(number) ) {
        // number of dupes is number of encounters minus one
        duplicates.merge(number, 1, Integer::sum);
      }
    }
    
    if ( duplicates.isEmpty() ) {
      System.out.println("No duplicates.");
    } else {
      for ( Map.Entry<Integer, Integer> duplicate : duplicates.entrySet() ) {
        // don't forget to add one to the dupe count to get total count
        System.out.println(format(duplicate.getKey()) + " " + (duplicate.getValue() + 1));
      }
    }
  }
  
  /** Formats a parsed phone number to its normal form (NNN-NNNN). */
  static String format(int phoneNumber) {
    final int prefix = phoneNumber / 10000;
    final int suffix = phoneNumber % 10000;
    return String.format("%03d-%04d", prefix, suffix);
  }
  
  /** Parses an unformatted phone number string, considering only the alphanumerics.
    * Does not guard for overflow. */
  static int parse(String number) {
    int retval = 0;
    for ( int i = 0; i < number.length(); i++ ) {
      int digit;
      final char c = number.charAt(i);
      switch ( c ) {
        case '0':
          digit = 0;
          break;
        
        case '1':
          digit = 1;
          break;
      
        case '2': case 'A': case 'B': case 'C':
          digit = 2;
          break;
          
        case '3': case 'D': case 'E': case 'F':
          digit = 3;
          break;
          
        case '4': case 'G': case 'H': case 'I':
          digit = 4;
          break;
          
        case '5': case 'J': case 'K': case 'L':
          digit = 5;
          break;
          
        case '6': case 'M': case 'N': case 'O':
          digit = 6;
          break;
          
        case '7': case 'P': case 'R': case 'S':
          digit = 7;
          break;
          
        case '8': case 'T': case 'U': case 'V':
          digit = 8;
          break;
          
        case '9': case 'W': case 'X': case 'Y':
          digit = 9;
          break;
          
        default:
          continue;
      }
      
      retval = 10 * retval + digit;
    }
    
    return retval;
  }
}

Source Link

created Oct 30, 2017 at 15:12

JvR

2.8k
12
25

String allocations

You make a number of allocations that may not be obvious:

public static String convert(String raw) {
    raw = raw.replaceAll("-", ""); // possibly new string, if contains hyphen
    raw = raw.toLowerCase(); // possibly new string, if contains uppercase
    String number = "";
    for(int i = 0; i < raw.length(); i++) {
        number += parse(raw.charAt(i)); // definitely new string, raw.length() times!
    }
    number = number.substring(0, 3) + "-" + number.substring(3); // three new strings: sub + sub + result
    return number;
}

String is immutable in Java, meaning any operations that result in different char data will result in a different string. String.substring also (usually) creates a new string.

The input "888-GLOP" ends up creating eleven new strings before returning its final, twelfth string!

`Map.get` + `Map.put` = `Map.merge`

if(!dict.containsKey(numbers[i])) { // Θ(log n)
    dict.put(numbers[i], 1); // Θ(log n)
} else {
    dict.put(numbers[i], dict.get(numbers[i]) + 1); // Θ(log n) + Θ(log n)
}

// -->

dict.merge(numbers[i], 1, Integer::sum);

Still, you are sorting/comparing strings each time you want to update your map. You could split into two parts: one part that checks whether you have already seen the input before (doesn't need to be sorted), and another that keeps track of your actual duplicates:

HashSet<String> seen;
TreeMap<String, Integer> duplicates;

// Set.add returns false if already contained
if ( !seen.add(number) ) { // Θ(1)
  duplicates.merge(number, 1, Integer::sum); // Θ(log n)
}

// printing later -- don't forget to add 1 to dupe count!
duplicates.forEach( (k,v) -> System.out.println( ... (v + 1) ... ); )

Alternatively, you can turn the data around:

HashMap<String, Integer> frequency;
TreeSet<String> duplicates;

if ( frequency.merge(number, 1, Integer::sum) > 1 ) { // Θ(1)
  duplicates.add(number); // Θ(log n)
}

duplicates.forEach( k -> System.out.println( ... frequency.get(k) ... ); )

Alternative implementation

Consider that:

Phone numbers have a normal form, which is NNN-NNNN, with N being a digit. This makes phone numbers contain 7 digits worth of information. That fits in an int. → Less memory usage, better cache usage.
You don't need to retain the original form. → We can use destructive methods.
Your incoming alphabet is limited: uppercase letters, decimal digits, and the hyphen. → switch-case and/or table parsing are viable.
You need to output only the duplicates. → We don't need to store everything, but we might end up having to.
You need to output the duplicates in lexicographical order. → We don't need to keep everything sorted; only the duplicates.

Leading to:

import java.util.*;

public class Main {
  public static void main(String[] args) {
    final Scanner in = new Scanner(System.in);
    int count = in.nextInt();
    
    /* We split duplicate detection in an unsorted part that just saves whether
     * we've seen it before, and a sorted part that stores actual duplicates in
     * lexicographical order. */
    final Set<Integer> seen = new HashSet<>();
    final NavigableMap<Integer, Integer> duplicates = new TreeMap<>();
    
    while ( count-- > 0 ) {
      String strnum = in.next();
      final Integer number = parse(strnum);
      
      if ( !seen.add(number) ) {
        // number of dupes is number of encounters minus one
        duplicates.merge(number, 1, Integer::sum);
      }
    }
    
    if ( duplicates.isEmpty() ) {
      System.out.println("No duplicates.");
    } else {
      for ( Map.Entry<Integer, Integer> duplicate : duplicates.entrySet() ) {
        // don't forget to add one to the dupe count to get total count
        System.out.println(format(duplicate.getKey()) + " " + (duplicate.getValue() + 1));
      }
    }
  }
  
  /** Formats a parsed phone number to its normal form (NNN-NNNN). */
  static String format(int phoneNumber) {
    return (phoneNumber / 10000) + "-" + (phoneNumber % 10000);
  }
  
  /** Parses an unformatted phone number string, considering only the alphanumerics.
    * Does not guard for overflow. */
  static int parse(String number) {
    int retval = 0;
    for ( int i = 0; i < number.length(); i++ ) {
      int digit;
      final char c = number.charAt(i);
      switch ( c ) {
        case '0':
          digit = 0;
          break;
        
        case '1':
          digit = 1;
          break;
      
        case '2': case 'A': case 'B': case 'C':
          digit = 2;
          break;
          
        case '3': case 'D': case 'E': case 'F':
          digit = 3;
          break;
          
        case '4': case 'G': case 'H': case 'I':
          digit = 4;
          break;
          
        case '5': case 'J': case 'K': case 'L':
          digit = 5;
          break;
          
        case '6': case 'M': case 'N': case 'O':
          digit = 6;
          break;
          
        case '7': case 'P': case 'R': case 'S':
          digit = 7;
          break;
          
        case '8': case 'T': case 'U': case 'V':
          digit = 8;
          break;
          
        case '9': case 'W': case 'X': case 'Y':
          digit = 9;
          break;
          
        default:
          continue;
      }
      
      retval = 10 * retval + digit;
    }
    
    return retval;
  }
}

Return to Answer

String allocations

Map.get + Map.put = Map.merge

Alternative implementation

`Map.get` + `Map.put` = `Map.merge`