Java 中 Int 的 PalindromeCheck 效率

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

我敢打赌第二种算法会更快，而且显然 space 效率更高。如果假设 n 是输入数字的位数，在第一个算法中：

Integer.toString 需要 n 步才能将其转换为 String.
palindromeCheck 需要 n / 2 次比较来检查它是否是回文。

但是，第二种算法将需要 n 步来计算反向数（仅涉及整数运算）并且仅需要 1 次比较来检查。

Answer 2

你为什么要重新发明轮子？

java.lang.StringBuilder已经提供了字符串反转的方法

String string = Integer.toString(10101);

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

Answer 3

我们试试吧。在下面的例子中（有一个特定的数字，在我的特定机器上......）：

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);

    }
}

Java 中 Int 的 PalindromeCheck 效率

PalindromeCheck efficiency for Int in Java

java

string

integer

palindrome