Эффективность PalindromeCheck для Int в Java

Question

Я построил два способа проверки палиндрома числа.Какой из них более эффективен?Под эффективностью я имею в виду время выполнения и распределение памяти.

Сначала я конвертирую целое число в строку и проверяю, является ли это палиндромом.Пример кода следующий:

public class Palindrome{

/*
Function palindromeCheck
Return type boolean
Parameters characterArray

Checks character array for palindrome
*/
 public static boolean palindromeCheck(char[] palinCheck){
    boolean palindrome = true;
    int firstLen = 0;
    int secondLen = palinCheck.length - 1;
    while(palindrome == true && firstLen < secondLen ){
        if(palinCheck[firstLen] != palinCheck[secondLen]){
            palindrome = false;
        }
        else{
            firstLen++;
            secondLen--;
        }
    } //end of while
    return palindrome;
} 

/*Main Function
Calls palinDromeCheck function
Prints results
*/
public static void main(String[] args){

    int palinCheck = 1221;
    String dipendra = Integer.toString(palinCheck);
    char[] dipendraChar = dipendra.toCharArray();
    System.out.println(palindromeCheck(dipendraChar));

}
}

Второй метод - без преобразования его в строку.

public class PalindromeNumber{


/*
    Function: PalindromeCheck
    parameters integer
    ReturnType: boolean

    Takes integer, checks if it is palindrome and returns accordingly
*/
public static boolean palindromeCheck(int number){
    int firstNumber = number;
    int secondNumber = 0;

    while(number >= 1){
        secondNumber = secondNumber* 10 + (number%10);
        number = number/10;
    }

    return (firstNumber==secondNumber) ? true:false;
}


public static void main(String[] args){
    System.out.println(palindromeCheck(111));
}
}

Answer 1

Почему вы заново изобретаете колесо?

java.lang.StringBuilder уже предоставляет метод перестановки строк

String string = Integer.toString(10101);

boolean palindrome = string.equalsIgnoreCase(new StringBuilder(string).reverse().toString());

Answer 2

Давайте попробуем.В следующем примере (с одним конкретным номером на моей конкретной машине ...):

• 580 мс - ваше первое решение
• 323 мс - ваше второе решение
• 1045 мс - решение BrentR

Примечание. Я немного изменил код (но не логику).Вам также следует позаботиться о пробелах и отступах.

public class Palindrome {

    public static boolean isPalindrome1(int n) {
        char a[] = Integer.toString(n).toCharArray();
        int i = 0;
        int j = a.length - 1;

        while (i < j) {
            if (a[i++] != a[j--]) return false;
        }
        return true;
    }

    public static boolean isPalindrome2(int n) {
        int p = n, q = 0;

        while (n > 0) {
            q = 10 * q + n % 10;
            n /= 10;
        }
        return p == q;
    }

    public static boolean isPalindrome3(int n) {
         String s = Integer.toString(n);
         return s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());
    }

    public static void main(String[] args) {
        final int m = 10000000;
        long t1, t2;
        boolean q;

        t1 = System.currentTimeMillis();
        for (int n = 0; n < m; n++) {
            q = isPalindrome1(123454321);
        }
        t2 = System.currentTimeMillis();
        System.out.println(t2 - t1);

        t1 = System.currentTimeMillis();
        for (int n = 0; n < m; n++) {
            q = isPalindrome2(123454321);
        }
        t2 = System.currentTimeMillis();
        System.out.println(t2 - t1);

        t1 = System.currentTimeMillis();
        for (int n = 0; n < m; n++) {
            q = isPalindrome3(123454321);
        }
        t2 = System.currentTimeMillis();
        System.out.println(t2 - t1);

    }
}

Answer 3

Бьюсь об заклад, второй алгоритм будет быстрее, и, очевидно, более экономно.Если вы предполагаете, что n будет количеством цифр входного числа, в первом алгоритме:

• Integer.toString требуется n шагов для его преобразования вString.
• palindromeCheck требует n / 2 сравнений, чтобы проверить, является ли это палиндромом.

Но для второго алгоритма потребуется n шагов для вычисления обратного числа (включая только целочисленные операции) и только 1 сравнение для проверки.