Số nguyên Số nguyên không có số trùng lặp trong java

Question

Mục tiêu của tôi là đảo ngược số nguyên không có số trùng lặp trong Java Làm cách nào để cải thiện độ phức tạp của mã hoặc có thuật toán tốt/chuẩn?

Trong trường hợp của chữ số trùng lặp, cần giữ gìn chữ số cuối cùng

public static void main(String[] args) { 
    int n = -19890; 
    System.out.println(reverseNumberWithoutDuplicate(n)); 
} 

public static int reverseNumberWithoutDuplicate(int number) { 
    boolean isNegative = (number < 0); 
    number = isNegative ? number * -1 : number; 

    Set<Character> lookup = new HashSet<>(); 

    StringBuffer sb = new StringBuffer(); 
    char[] digits = String.valueOf(number).toCharArray(); 
    for (int i = digits.length - 1; i >= 0; --i) { 
     if (lookup.contains(digits[i])) { 
      continue; 
     } 
     sb.append(digits[i]); 
     lookup.add(digits[i]); 
    } 
    return isNegative ? Integer.parseInt(sb.toString()) * -1 : Integer.parseInt(sb.toString()); 
} 

sản lượng dự kiến: -981

Answer 1

Độ phức tạp là tốt. Mặc dù nó có thể được tối ưu hóa.

Sử dụng StringBuilder tốt hơn so với StringBuffer cũ hơn, có chi phí không cần thiết (đối với độ an toàn của luồng).

Sau đó, dữ liệu có thể vẫn là số và đối với mười chữ số có thể, BitSet là tốt.

public static int reverseNumberWithoutDuplicate(int number) { 
    if (number == Integer.MIN_VALUE) { 
     // -2147483648 is a special case, not negatable. 
     return -8463712; 
    } 
    boolean isNegative = number < 0; 
    number = isNegative ? -number : number; 

    BitSet usedDigits = new BitSet(10); 
    int reversedNumber = 0; 
    while (number != 0) { 
     int digit = number % 10; 
     number /= 10; 
     if (!usedDigits.get(digit)) { 
      usedDigits.set(digit); 
      reversedNumber = 10 * reversedNumber + digit; 
     } 
    } 
    return isNegative ? -reversedNumber : reversedNumber; 
} 

Answer 2

Hãy xây dựng một giải pháp từng bước. Hàm sau đảo ngược chữ số của số dương.

int reverseNumber(int number) { 
    int answer = 0; 
    for (int n = number; n != 0; n /= 10) { 
     // Digits are taken from least significant to most significant 
     int digit = n % 10; 
     // And added the other way round 
     answer = answer * 10 + digit; 
    } 
    return answer; 
} 

Mã này có thể dễ dàng thích nghi để làm việc với số âm để:

int reverseNumber(int number) { 
    if (number < 0) { 
     return -reverseNumber(-number); 
    } 
    // The rest is the same 

mục tiêu tiếp theo của chúng tôi - bỏ qua chữ số trùng lặp. Chúng tôi sẽ theo dõi danh sách các chữ số đã xem trong số boolean[] seen.

private static int reverseNumberWithoutDuplicate(int number) { 
    if (number < 0) { 
     return -reverseNumberWithoutDuplicate(-number); 
    } 

    boolean[] seen = new boolean[10]; 
    int answer = 0; 
    for (int n = number; n != 0; n /= 10) { 
     int digit = n % 10;    
     if (!seen[digit]) { 
      seen[digit] = true; 
      answer = answer * 10 + digit; 
     } 
    } 
    return answer; 
}