Java Program to Check If Array Is Palindrome

回文数组（Palindromic Array）是指从前往后读和从后往前读都一样的数组，类似于回文字符串。检查数组是否为回文，需要从数组的两端开始对称地比较元素。Java程序通过遍历数组，比较第一个和最后一个元素，第二个和倒数第二个元素，以此类推，确保了简单高效的回文结构检查。

输入

数组: [1, 2, 3, 2, 1]

输出

该数组是回文数组。

解释

输出表明该数组是回文数组，因为它的正读和反读都一样。程序首先比较第一个和最后一个元素，然后是第二个和倒数第二个元素，以此类推。由于所有对应元素对都匹配，因此确认该数组是回文数组。

输入

数组: [1, 2, 3, 4, 5]

输出

该数组不是回文数组。

解释

输出表明该数组不是回文数组，因为从两端读取时，元素并不对称。例如，第一个元素（1）与最后一个元素（5）不匹配，其他元素对也是如此。因此，该数组不具备回文结构。

方法一：使用双指针技术

算法

步骤 1：初始化指针：使用两个指针开始： start 指向第一个元素（索引 0），end 指向最后一个元素（索引 array.length - 1）。

步骤 2：遍历数组： 使用循环同时将 start 指针向前移动，将 end 指针向后移动。

步骤 2.1：检查空数组： 在遍历数组之前，检查数组是否为空（即 array.length == 0）。如果数组为空，可以认为它是回文数组，因为没有元素可以比较。立即返回数组是回文数组。此步骤处理了输入为空数组的边缘情况，确保程序不会尝试执行不必要的操作。

步骤 3：比较元素：对于每次迭代： 检查 start 处的元素是否等于 end 处的元素。如果不相等，则得出结论该数组不是回文数组，并停止该过程。

步骤 4：向内移动指针： 将 start 增加 1，将 end 减 1，以比较下一对元素。

步骤 4.1：检查不匹配时的提前退出： 在向内移动指针之前，检查 start 和 end 指针处的元素是否匹配。如果不匹配，立即退出循环并返回数组不是回文数组。这可以避免一旦检测到不匹配就进行不必要的比较。通过及早识别不匹配，可以节省时间并避免执行任何进一步的检查。

步骤 5：直到中间进行检查： 继续比较，直到 start 指针不再小于 end 指针。如果所有对都匹配，则该数组是回文数组。

步骤 5.1：处理单元素数组的边缘情况： 在继续比较之前，检查数组是否只有一个元素（即 start == end）。在这种情况下，该数组是回文数组，因为单个元素正读和反读都一样。立即返回数组是回文数组，无需进一步处理。此步骤确保我们有效地处理非常小的数组的边缘情况。

步骤 6：返回结果： 如果未发现不匹配，则返回数组是回文数组。否则，返回它不是回文数组。

文件名: PalindromicArray.java

输出

 
The array is palindromic.   

复杂度分析

时间复杂度

双指针技术的 O(n) 时间复杂度，其中 n 是数组的长度。这是因为我们只遍历数组一次，比较开头和结尾的元素，然后向内移动。该算法以线性时间有效地检查回文结构。

空间复杂度

双指针技术的 O(1) 空间复杂度，因为它只需要恒定的额外空间。该算法使用两个指针来遍历数组，并且不需要额外的 数据结构 或内存分配，因此对于检查回文数组来说，它是空间高效的。

方法二：使用反向数组比较

使用反向数组比较涉及创建原始数组的反向副本，并逐个元素进行比较。如果原始数组中的所有元素都与其反向数组中的对应元素匹配，则该数组是回文数组。该方法通过直接比较有效地检查对称性。

算法

步骤 1：处理边缘情况： 在处理数组之前，请考虑以下几点

空数组： 如果数组没有元素（array.length == 0），则它自然是回文数组，因为没有值可以比较。

单元素数组： 如果数组只有一个元素（arra.length == 1），则它本身就是回文数组，因为单个值正读和反读都一样。

步骤 2：创建反向副本： 初始化一个与原始数组大小相同的空数组（reversedArray）。使用循环，从最后一个索引开始，向第一个索引移动，以反向顺序遍历原始数组。

在每次迭代中，将原始数组中的当前元素复制到反向数组中的相应位置。此步骤可确保您拥有原始数组的反向版本以进行比较。

步骤 2.1：构建反向数组： 初始化一个与原始数组大小相同的空数组。从最后一个元素到第一个元素遍历原始数组，并将每个元素按顺序复制到反向数组中。这确保了反向数组是原始数组的精确镜像，为下一步的比较做好了准备。

步骤 3：比较两个数组： 同时遍历原始数组和反向数组。对于每个索引：比较原始数组的元素与反向数组的对应元素。如果任何一对元素不相等，则停止比较，并得出结论该数组不是回文数组。

步骤 3.1：直接对称比较： 遍历数组的前半部分，将索引 i 处的每个元素与其在 array.length - 1 - i 处的对称对应项进行比较。如果任何一对元素不匹配，则得出结论该数组不是回文数组，并提前退出。如果所有比较都成功，则确认该数组是回文数组。该方法避免了创建反向数组，只专注于必要的比较，从而提高了效率。

步骤 4：返回结果： 如果在比较过程中所有元素都匹配，则得出结论该数组是回文数组。如果发现不匹配，则该数组不是回文数组。

步骤 4.1：不匹配时提前退出： 在比较原始数组和反向数组时，如果对应位置的任何一对元素不匹配，请立即停止进一步的比较，并得出结论该数组不是回文数组。这可以避免在找到不匹配后进行不必要的检查，从而提高算法的整体效率。

步骤 5：优化特殊情况： 为了提高效率，请提前处理小型数组

空数组： 立即返回它是回文数组，无需进一步处理，因为没有元素可以比较。

单元素数组： 直接得出它是回文数组，因为单个值正读和反读都一样。

文件名: PalindromicArrayAlternative.java

输出

 
The array is palindromic.   

复杂度分析

时间复杂度

反向数组比较方法的 O(n) 时间复杂度，其中 n 是数组的长度。创建反向数组需要遍历所有元素一次，而将原始数组与反向数组进行比较则需要另一次完整遍历。因此，总复杂度保持线性 O(n)。

空间复杂度

反向数组比较方法的 O(n) 空间复杂度，其中 n 是数组的长度。这是因为创建了一个与原始数组大小相同的附加数组来存储反向元素。除此之外，没有使用其他重要的辅助空间。