题目描述 给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。（测试用例仅做参考，我们会根据代码质量进行评分） 输入描述： 第一行输入整数n。(1<=n<=1000)表示数组大小 第二行输入n个整数a.(1<=n<=100) 输出描述： 输出重排之后的数组。

<think>好的，我现在需要帮用户解决一个整数数组重新排列的问题，要求奇数在前半部分，偶数在后半部分，并且奇数和偶数的相对顺序要保持原数组的顺序，同时空间复杂度为O(1)。用户还要求用Java语言实现。 首先，我得回忆一下之前的讨论。之前的解决方案是使用双指针交换法，时间复杂度O(n)，空间O(1)，但那不保持相对顺序。现在用户的新要求是保持相对顺序，所以之前的解法不适用了。 保持相对顺序通常意味着不能使用交换的方法，因为交换会打乱顺序。这时候可能需要类似插入排序的思路，或者通过两次遍历来分别处理奇数和偶数。但题目要求空间复杂度为O(1)，所以不能使用额外的数组来存储结果。 可能的思路有两种： 1. 类似插入排序的方法：遍历数组，当遇到奇数时，将其移动到已处理奇数的末尾。这需要移动元素，可能的时间复杂度是O(n²)，但空间是O(1)。 2. 两次遍历法：第一次遍历收集奇数，第二次收集偶数，但需要原地操作，这可能比较困难，因为数组长度固定，如何原地覆盖而不丢失数据呢？ 这里可能需要优化。比如，先记录奇数的数量，然后在第二次遍历时把偶数放到奇数的后面。但如何同时保持顺序呢？ 或者，可以分两步处理：先处理所有的奇数，保持它们的顺序，再处理所有的偶数，保持它们的顺序。但如何在原数组上操作呢？ 比如，使用两个指针，一个指向当前应该放置奇数的位置，另一个遍历数组，每次找到奇数就放到前面，然后移动指针。剩下的位置自然就是偶数，但需要同样处理。不过这样做的话，偶数部分的顺序可能无法保持，因为当移动奇数时，后面的元素会前移，导致偶数的顺序被打乱。 例如，考虑数组[1,2,3,4,5]，当把奇数1,3,5移到前面，剩下的位置是2和4，它们保持原来的顺序。但如果在处理过程中需要覆盖元素，可能会导致数据丢失。比如，如果直接覆盖的话，后面的元素会被覆盖掉。 所以，可能需要一种方法，在不使用额外空间的情况下，通过多次遍历或者某种交换方式来保持顺序。 另一种思路是使用类似于稳定排序的方法，比如冒泡排序的思路，将奇数逐个冒泡到前面，同时保持偶数的相对顺序。但这样的时间复杂度会很高，O(n²)，但对于空间复杂度是O(1)。 用户可能希望有一个时间复杂度较低的方法，但根据问题要求，可能只能接受O(n²)的时间复杂度，因为要保持顺序且不能使用额外空间。 例如，参考插入排序的思路： - 维护一个指针insertPos，初始为0，表示当前奇数应该插入的位置。 - 遍历数组，当遇到一个奇数时，将其插入到insertPos的位置，并将insertPos加1。但插入操作需要将后面的元素都后移一位，这样时间复杂度为O(n²)，但空间是O(1)。 比如，数组是[2,1,3,4,5]，第一次遇到1时，需要将1插入到位置0，后面的元素（包括后面的2）都后移，这会导致大量元素移动，时间复杂度很高，但符合空间要求。 或者，可以优化移动的次数，比如当找到奇数时，与前面的元素交换，直到到达正确的位置。例如，类似冒泡的方式，将奇数逐个前移，直到遇到前面的奇数或开始的位置。这样也能保持偶数的相对顺序，因为偶数不会被交换到后面，除非它们后面有奇数。 例如，考虑数组[2,4,1,3,5]，遍历时，当遇到1，就不断与前一个元素交换，直到到达前面奇数的末尾或数组开头。这样1会交换到第一个位置，而原来的2和4会被后移，变成[1,2,4,3,5]。然后遇到3，同样交换到1后面，变成[1,3,2,4,5]。最后处理5，交换到3后面。这样奇数的顺序保持，偶数的顺序也保持。 这种方法的时间复杂度同样是O(n²)，但可能更高效一些，因为每个奇数只需要移动到前面的位置，而不需要每次都移动整个后面的数组。 因此，这样的算法是可行的，虽然时间效率不高，但符合题目要求。 现在，需要用Java实现这个思路。具体步骤： 1. 初始化insertPos为0，表示当前奇数应该插入的位置。 2. 遍历数组，对于每个元素nums[i]： a. 如果是奇数，将其从当前位置i移动到insertPos的位置。 b. 如何移动？可以通过交换相邻元素的方式，将nums[i]逐步交换到insertPos的位置，这样其他元素的相对顺序不会改变。 c. 例如，i=2，insertPos=0，那么交换nums[2]和nums[1]，再交换nums[1]和nums[0]，这样nums[2]的元素就被移动到位置0，同时原来的0和1位置的元素后移一位，保持偶数的顺序。 d. 但这样的交换次数较多，时间复杂度高。 或者，可以采用另一种方式：当找到一个奇数时，将其前面的所有偶数后移一位，然后将该奇数放到insertPos的位置。例如： 假设当前insertPos是k，当在位置i找到一个奇数时，将数组从k到i-1的元素后移一位，然后将该奇数放到k的位置。这需要O(n)的时间，整体时间复杂度是O(n²)，空间O(1)。 但这样的操作在Java中如何实现呢？比如，数组是原始数组，不能使用额外的空间，只能通过循环移动。 例如，数组是[2,4,1,3,5]，insertPos=0，i=2（元素1是奇数）。需要将2和4后移，然后插入1到位置0： 1. 保存1到临时变量temp。 2. 将数组从位置0到1的元素（2,4）后移一位到位置1到2。 3. 将temp放入位置0。 结果数组变为[1,2,4,3,5]。 这样的操作需要移动元素，每次移动i - insertPos次。对于每个奇数，这样的移动次数是O(n)，所以总的时间复杂度是O(n²)。 这种方法的实现步骤： - 遍历数组，找到每个奇数。 - 对于每个奇数，记录其值，然后将前面的偶数后移，最后将该奇数放到insertPos的位置。 - insertPos递增。 这样的方法虽然时间复杂度高，但符合空间要求，并且保持顺序。 现在，如何在Java中实现这个？ 例如： public class Solution { public void reorderOddEven(int[] nums) { int insertPos = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] % 2 != 0) { // 奇数 int temp = nums[i]; // 将insertPos到i-1的元素后移一位 for (int j = i; j > insertPos; j--) { nums[j] = nums[j - 1]; } nums[insertPos] = temp; insertPos++; } } } } 这样，对于每个奇数，将其前面的偶数后移，然后插入到正确的位置。这样可以保证奇数的相对顺序，同时偶数的相对顺序也保持不变，因为它们只是被后移，没有被交换。 例如，测试数组[2,1,3,4,5]： i=0，元素2是偶数，不处理。 i=1，元素1是奇数。insertPos=0。需要将i=1的元素移动到0的位置。将元素2后移到1的位置，插入1到0。数组变成[1,2,3,4,5]。insertPos=1。 i=2，元素3是奇数。insertPos=1。将元素2后移到2的位置，插入3到1的位置。数组变成[1,3,2,4,5]。insertPos=2。 i=3，元素2是偶数，不处理。 i=4，元素5是奇数。insertPos=2。将元素2和4后移，插入5到2的位置。数组变成[1,3,5,2,4]。 最终结果是[1,3,5,2,4]，奇偶顺序都保持原顺序。 这样的实现确实满足要求，时间复杂度为O(n²)，空间O(1)。 但用户的问题可能需要更优化的方法，例如是否有O(n)的时间复杂度且O(1)空间的解法？但根据常见的算法知识，保持稳定性的原地排序通常需要O(n²)时间，比如冒泡、插入排序。所以可能这就是最优解。 因此，最终的Java代码应该是这样的插入方式。需要验证一下是否正确。 另一个测试用例：输入[3,1,2,4,6,5]，原数组奇数顺序3,1,5，偶数顺序2,4,6。处理后的数组应为3,1,5,2,4,6。按照上述代码： i=0，元素3是奇数，插入到0，不需要移动，insertPos=1. i=1，元素1是奇数，插入到1，不需要移动，insertPos=2. i=2，元素2是偶数，跳过。 i=3，元素4是偶数，跳过。 i=4，元素6是偶数，跳过。 i=5，元素5是奇数。insertPos=2，需要将位置5的元素移动到2的位置。将位置2到4的元素（2,4,6）后移到3到5的位置，然后把5放在位置2。数组变为[3,1,5,2,4,6]，正确。 所以，代码是正确的。这样就能满足用户的需求。</think>```java public class OddEvenSorter { /** * 保持奇偶相对顺序的重排列方法 * 时间复杂度：O(n²) 空间复杂度：O(1) * @param nums 待处理数组 */ public static void reorderOddEven(int[] nums) { int insertPos = 0; // 奇数插入位置标记 for (int i = 0; i < nums.length; i++) { if (isOdd(nums[i])) { // 发现奇数时执行插入操作 int temp = nums[i]; // 将当前位置到插入位置之间的元素后移 shiftElements(nums, insertPos, i); nums[insertPos] = temp; insertPos++; } } } /** * 元素后移操作 * @param nums 数组 * @param start 起始位置 * @param end 结束位置 */ private static void shiftElements(int[] nums, int start, int end) { if (end - start >= 0) { System.arraycopy(nums, start, nums, start + 1, end - start); } } /** * 判断奇数的工具方法 * @param num 待判断数字 * @return 是否为奇数 */ private static boolean isOdd(int num) { return (num & 1) == 1; } public static void main(String[] args) { // 测试用例 int[] testCase = {2, 1, 3, 4, 5, 6}; reorderOddEven(testCase); System.out.println(Arrays.toString(testCase)); // 输出：[1, 3, 5, 2, 4, 6] } } ``` ### 算法解析 1. **核心思想** - **插入排序变体**：通过模拟插入排序的机制，保持元素相对顺序 - **双指针控制**：使用`insertPos`标记奇数应该插入的位置 2. **关键操作流程** 1. 遍历数组，当发现奇数时： - 保存当前奇数值到临时变量 - 将该位置之前的元素整体后移一位 - 将保存的奇数插入到`insertPos`位置 - 更新插入位置标记 3. **复杂度分析** - 时间复杂度：$O(n^2)$ 最坏情况下每个奇数都需要移动其前面的所有元素 - 空间复杂度：$O(1)$ 仅使用固定数量的临时变量 4. **算法优势** - 完全原地操作，不占用额外空间 - 严格保持奇偶元素的原始相对顺序 - 适用于内存敏感的场景 ### 拓展优化思路 对于需要更高性能的场景，可以结合以下方法进行优化（需权衡空间复杂度）： **链表重排法**（空间复杂度$O(n)$）： ```java public static int[] optimizedReorder(int[] nums) { List<Integer> oddList = new ArrayList<>(); List<Integer> evenList = new ArrayList<>(); for (int num : nums) { if (isOdd(num)) { oddList.add(num); } else { evenList.add(num); } } oddList.addAll(evenList); return oddList.stream().mapToInt(i->i).toArray(); } ``` **位操作优化**（保持原地操作）： ```java public static void bitwiseReorder(int[] nums) { int writePointer = 0; for (int readPointer = 0; readPointer < nums.length; readPointer++) { if ((nums[readPointer] & 1) == 1) { int temp = nums[writePointer]; nums[writePointer++] = nums[readPointer]; nums[readPointer] = temp; } } } ```

### 实现奇数位逆序和偶数位顺序链表 为了实现这一功能，可以采用双指针的方法来处理输入整数的不同位置上的数字。具体来说： 对于给定的一个整数，先将其转换成字符串形式以便于逐位访问各个数字。接着通过遍历该字符串并区分索引是奇数还是偶数来进行不同操作：当遇到奇数索引时，将对应的字符加入到用于构建逆序部分的结果列表中；而对于偶数索引，则直接追加至另一个用于保存正向序列的部分。 完成上述过程之后，需要反转之前收集起来的代表奇数位的数据结构（如数组），从而得到真正的逆序排列。最后一步就是依次连接这些节点形成完整的链表对象[^1]。 下面是一个Python版本的具体实现方案： ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def create_linked_list_from_number(number: int) -> tuple[ListNode, ListNode]: str_num = str(number)[::-1] odd_head = None even_head = None current_odd = None current_even = None for i, digit_char in enumerate(str_num): new_node = ListNode(int(digit_char)) if i % 2 == 0: # Even index means it should be added to the end of 'even' list. if not even_head: even_head = new_node current_even = even_head else: current_even.next = new_node current_even = current_even.next elif i % 2 != 0: # Odd index means adding at head of 'odd' list for reverse order. if not odd_head: odd_head = new_node current_odd = odd_head else: temp = odd_head odd_head = new_node odd_head.next = temp return odd_head, even_head number = 9876543210 odd_part, even_part = create_linked_list_from_number(number) print("Odd part (reversed): ", end="") while odd_part: print(f"{odd_part.val} -> " if odd_part.next else f"{odd_part.val}", end="") odd_part = odd_part.next print("\nEven part (ordered): ", end="") while even_part: print(f"{even_part.val} -> " if even_part.next else f"{even_part.val}", end="") even_part = even_part.next ``` 这段代码定义了一个`ListNode`类用来表示单个链接节点，并实现了函数`create_linked_list_from_number()`接收一个整型参数作为输入，返回两个链表头结点组成的元组，第一个元素指向由原数中的奇数位构成的新链表头部（按原始次序相反的方向建立），第二个元素则指向由偶数位组成的新链表头部（保持原有相对位置）。此外还包含了测试用例展示如何调用这个方法以及打印输出结果。