Java 中偶数索引处的偶数和奇数索引处的奇数

2025年1月6日 | 阅读 12 分钟

将偶数安排在偶数索引，奇数安排在奇数索引的过程，需要对数组中的数字进行重新排列，使得偶数位于偶数索引（0, 2, 4, . . .）上，奇数位于奇数索引（1, 3, 5, . . .）上，确保数字和它们的位置具有相同的奇偶性。

示例 1

输入

输出

10 9 18 7 20 19 4 13 14 21

解释

The output array is {10, 9, 18, 7, 20, 19, 4, 13, 14, 21}, with even numbers at even indices and odd numbers at odd indices, ensuring the required output order from input array.

示例 2

输入

输出

2 5 8 7 6 1 4

解释

The output array is {2, 5, 8, 7, 6, 1, 4}, where even numbers are at even indices and odd numbers are at odd indices, maintaining the required order of elements from the input array.

方法一：双指针法

双指针法是数组操作问题中的一种常用技术，特别适用于需要根据特定条件交换或重新排序元素的数组重排场景。双指针法涉及使用两个指针同时遍历数组，通常从相反的两端开始，或者以不同的增量移动，我们将使用两个指针来跟踪偶数和奇数的下一个位置。

算法

步骤 1： 输入数组 arr[]，并初始化两个指针 evenInd 和 oddInd，分别用于跟踪偶数和奇数索引：evenInd 从索引 0 开始，oddInd 从索引 1 开始。

步骤 2： While 循环：进入一个 while 循环，直到 evenInd 或 oddInd 超出数组边界为止。

步骤 3： 偶数索引移动：在循环内部，使用嵌套的 while 循环：将 evenInd 移动到下一个偶数。

步骤 3.1： evenInd 每次增加 2，直到它到达一个偶数或超出数组边界。如果 evenInd 当前位置的元素已经是偶数，则无需移动。

步骤 4： 奇数索引移动：类似地，将 oddInd 移动到下一个奇数：oddInd 每次增加 2，直到它到达一个奇数或超出数组边界。如果 oddInd 当前位置的元素已经是奇数，则无需移动。

步骤 5： 交换操作：如果 evenInd 和 oddInd 都在数组边界内：交换这两个索引处的元素，将 evenInd 处找到的偶数放到偶数索引上，将 oddInd 处找到的奇数放到奇数索引上。

步骤 6： 终止：如果 evenInd 或 oddInd 中的任何一个超出了数组边界，则退出循环。

步骤 7： 循环完成后，数组将被重新排列，偶数位于偶数索引，奇数位于奇数索引。打印或返回修改后的数组作为输出。

文件名： EvenOddIndex.java

public class EvenOddIndex {
    // Function to rearrange odd and even numbers
    public static void arrangeEvenOdd(int arr[]) {
        // Initialize two pointers to track even and odd indices
        int evenInd = 0;
        int oddInd = 1;
        // Traverse the array
        while (true) {
            // Move evenInd to the next even number
            while (evenInd < arr.length && arr[evenInd] % 2 == 0) {
                evenInd += 2;
            }
            // Move oddInd to the next odd number
            while (oddInd < arr.length && arr[oddInd] % 2 == 1) {
                oddInd += 2;
            }
            // If both evenInd and oddInd are within array bounds, swap the numbers
            if (evenInd < arr.length && oddInd < arr.length) {
                int temp = arr[evenInd];
                arr[evenInd] = arr[oddInd];
                arr[oddInd] = temp;
            } else {
                // If any pointer exceeds array bounds, break the loop
                break;
            }
        }
    }
    // Function to print the array
    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // Main method
    public static void main(String[] args) {
        // Example array
        int[] arr = {3, 8, 5, 2, 6, 9, 4, 7};
        // Printing original array
        System.out.print("Original Array: ");
        printArray(arr);
        // Rearranging the array
        arrangeEvenOdd(arr);
        // Printing modified array
        System.out.print("Modified Array: ");
        printArray(arr);
    }
}

输出

 
Original Array: 3 8 5 2 6 9 4 7 
Modified Array: 8 3 2 5 6 9 4 7

时间复杂度

该算法使用两个指针 evenInd 和 oddInd 遍历数组一次，根据特定条件向前移动。随着数组大小的增加，线性遍历所需的时间也成比例增加。时间复杂度与输入数组大小 n 成正比，即 O(n)。

空间复杂度

该算法使用恒定的额外空间，与输入数组的大小无关，即 O(1)。它只需要固定数量的变量来跟踪指针（evenInd 和 oddInd）以及一些用于交换元素的临时空间。使用的空间不会随着输入数组的大小而增长。

方法二：直接交换法

直接交换法是一种用于将数组中的偶数安排在偶数索引，奇数安排在奇数索引的技术。该方法简化了逻辑，直接在正确的位置交换元素，而无需使用嵌套循环或多个指针。

算法

步骤 1： 输入数组 arr[]，并初始化两个指针 i 和 j，分别设置为 0 和 1，表示奇数和偶数的起始索引。

步骤 2： While 循环：进入一个 while 循环，遍历数组，直到 i 或 j 超出数组边界。

步骤 3： 奇偶索引移动：在循环内，检查条件：如果 i 位置的数字是奇数，而 j 位置的数字是偶数，则交换它们，然后移动到下一对索引（i += 2, j += 2）。

步骤 4： 如果 i 位置的数字是偶数，则移动到下一个奇数索引（i += 2）。如果 j 位置的数字是奇数，则移动到下一个偶数索引（j += 2）。

步骤 5： 当 i 或 j 超出数组边界时退出循环，并返回重新排列的数组。

文件名： DirectSwapApproach.java

import java.util.Arrays;
public class DirectSwapApproach {
    public static void main(String[] args) {
        // Example arrays
        int[] arr1 = {3, 6, 12, 1, 5, 8};
        int[] arr2 = {10, 9, 7, 18, 13, 19, 4, 20, 21, 14};
        // Arrange arrays and print results
        int[] arrangedArr1 = arrangeArray(arr1);
        System.out.println("Arranged Array 1: " + Arrays.toString(arrangedArr1));
        int[] arrangedArr2 = arrangeArray(arr2);
        System.out.println("Arranged Array 2: " + Arrays.toString(arrangedArr2));
    }
    // Function to arrange the array such that odd numbers
    // are at odd indices and even numbers are at even indices
    public static int[] arrangeArray(int[] arr) {
        int i = 0; // starting index for odd numbers
        int j = 1; // starting index for even numbers
        int n = arr.length; // length of the array
        // Traverse the array until either i or j exceeds the array bounds
        while (i < n && j < n) {
            // If the number at i is odd and the number at j is even, swap them
            if (arr[i] % 2 != 0 && arr[j] % 2 == 0) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i += 2; // move to next odd index
                j += 2; // move to next even index
            } else {
                // If the number at i is even, move to the next odd index
                if (arr[i] % 2 == 0) {
                    i += 2;
                }
                // If the number at j is odd, move to the next even index
                if (arr[j] % 2 != 0) {
                    j += 2;
                }
            }
        }
        return arr; // return the arranged array
    }
}

输出

 
Arranged Array 1: [6, 3, 12, 1, 8, 5]
Arranged Array 2: [10, 9, 18, 7, 20, 19, 4, 13, 14, 21]

时间复杂度

该算法使用两个指针 i 和 j 遍历数组一次，根据特定条件向前移动。随着数组大小的增加，线性遍历所需的时间也成比例增加。时间复杂度与输入数组大小 n 成正比，即 O(n)。

空间复杂度

该算法具有恒定的空间复杂度 O(1)；因为它只使用固定量的额外空间，与输入数组的大小无关。它不使用任何随着输入大小而增长的额外数据结构。

方法三：额外空间法

额外空间法是一种将数组中的元素重新排列，使得偶数放置在偶数索引，奇数放置在奇数索引的方法。该方法利用额外的空间来临时分开存储偶数和奇数，然后再将它们按照所需顺序合并回原始数组。

算法

步骤 1： 创建两个空列表 evenList 和 oddList，分别用于临时存储偶数和奇数。

步骤 2： 初始化一个与输入数组长度相同的数组 arrangedArr，用于存储最终结果。

步骤 3： 分离阶段：从头到尾遍历输入数组 arr。对于数组中的每个元素：检查元素是偶数还是奇数。

步骤 4： 如果元素是偶数，则将其添加到 evenList。如果元素是奇数，则将其添加到 oddList。

步骤 5： 合并阶段：初始化两个索引变量 evenIndex 和 oddIndex，分别设置为 0 和 1。

步骤 6： 遍历 evenList：将 evenList 的每个元素放置到 arrangedArr 中由 evenIndex 指定的位置。放置每个元素后，将 evenIndex 增加 2。

步骤 7： 遍历 oddList：将 oddList 的每个元素放置到 arrangedArr 中由 oddIndex 指定的位置。

步骤 8： 放置每个元素后，将 oddIndex 增加 2。返回 arrangedArr 作为最终重新排列的数组。

文件名： ExtraSpaceApproach.java

import java.util.ArrayList;
import java.util.List;
public class ExtraSpaceApproach {
    public static void main(String[] args) {
        // Example arrays
        int[] arr1 = {3, 6, 12, 1, 5, 8};
        int[] arr2 = {10, 9, 7, 18, 13, 19, 4, 20, 21, 14};
        // Arrange arrays and print results
        int[] arrangedArr1 = arrangeArray(arr1);
        System.out.println("Arranged Array 1: " + arrayToString(arrangedArr1));
        int[] arrangedArr2 = arrangeArray(arr2);
        System.out.println("Arranged Array 2: " + arrayToString(arrangedArr2));
    }
    // Function to arrange the array such that odd numbers
    // are at odd indices and even numbers are at even indices
    public static int[] arrangeArray(int[] arr) {
        // Lists to store even and odd numbers
        List<Integer> evenList = new ArrayList<>();
        List<Integer> oddList = new ArrayList<>();
        // Traverse the original array and separate even and odd numbers
        for (int num : arr) {
            if (num % 2 == 0) {
                evenList.add(num); // Add even numbers to even list
            } else {
                oddList.add(num); // Add odd numbers to odd list
            }
        }
        // Merge even and odd lists to form the arranged array
        int[] arrangedArr = new int[arr.length];
        int evenIndex = 0;
        int oddIndex = 1;
        for (int num : evenList) {
            arrangedArr[evenIndex] = num;
            evenIndex += 2; // Move to next even index
        }
        for (int num : oddList) {
            arrangedArr[oddIndex] = num;
            oddIndex += 2; // Move to next odd index
        }
        return arrangedArr; // return the arranged array
    }
    // Function to convert array to string for printing
    public static String arrayToString(int[] arr) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

输出

Arranged Array 1: [6, 3, 12, 1, 8, 5]
Arranged Array 2: [10, 9, 18, 7, 4, 13, 20, 19, 14, 21]

时间复杂度

该算法遍历整个输入数组一次以分离偶数和奇数，时间复杂度为 O(n)。该算法遍历偶数列表和奇数列表，将它们的元素放置到结果数组的适当位置，时间复杂度也为 O(n)，其中 n 是输入数组的长度。因此，总时间复杂度为 O(n)。

空间复杂度

额外空间法的空间复杂度为 O(n)，其中 n 是输入数组中的元素数量。这是因为该算法使用两个额外的列表（evenList 和 oddList）来存储偶数和奇数。在最坏的情况下，这两个列表的大小之和将等于输入数组的大小。

方法四：排序法

排序法是一种利用排序来方便地将数组中的偶数安排在偶数索引，奇数安排在奇数索引的方法。该方法涉及对数组进行排序以分离偶数和奇数，然后将它们放置在适当的索引上。

算法

步骤 1： 定义一个函数 arrangeArray，它接受一个整数数组作为输入。定义一个 main 方法，使用示例数组测试该函数。

步骤 2： 排序数组：使用 Arrays.sort(arr) 对输入数组进行排序。这将确保所有偶数和奇数都被分组在一起。

步骤 3： 设置指针：初始化两个指针：evenIndex 设置为 0，oddIndex 设置为 1。这些指针将用于在结果数组中将偶数和奇数放置到各自的索引上。

步骤 4： 创建结果数组：创建一个与输入数组长度相同的新数组 arrangedArr，用于存储重新排列的元素。

步骤 5： 放置元素：遍历排序数组中的每个元素：如果元素是偶数，则将其放置在结果数组中下一个可用的偶数索引（evenIndex）上，并将 evenIndex 增加 2。

步骤 6： 如果元素是奇数，则将其放置在结果数组中下一个可用的奇数索引（oddIndex）上，并将 oddIndex 增加 2。返回结果数组 arrangedArr。

文件名： SortingApproach.java

import java.util.Arrays;
public class SortingApproach {
    public static void main(String[] args) {
        // Example arrays
        int[] arr1 = {3, 6, 12, 1, 5, 8};
        int[] arr2 = {10, 9, 7, 18, 13, 19, 4, 20, 21, 14};
        // Arrange arrays and print results
        int[] arrangedArr1 = arrangeArray(arr1);
        System.out.println("Arranged Array 1: " + arrayToString(arrangedArr1));
        int[] arrangedArr2 = arrangeArray(arr2);
        System.out.println("Arranged Array 2: " + arrayToString(arrangedArr2));
    }
    // Function to arrange the array such that odd numbers
    // are at odd indices and even numbers are at even indices
    public static int[] arrangeArray(int[] arr) {
        // Step 1: Sort the array
        Arrays.sort(arr);
        // Step 2: Create two pointers for even and odd indices
        int evenIndex = 0;
        int oddIndex = 1;
        // Step 3: Create a new array to store the result
        int[] arrangedArr = new int[arr.length];
        // Step 4: Place sorted elements at correct indices
        for (int num : arr) {
            if (num % 2 == 0) {
                // Place even number at the next available even index
                if (evenIndex < arr.length) {
                    arrangedArr[evenIndex] = num;
                    evenIndex += 2;
                }
            } else {
                // Place odd number at the next available odd index
                if (oddIndex < arr.length) {
                    arrangedArr[oddIndex] = num;
                    oddIndex += 2;
                }
            }
        }
        return arrangedArr;
    }
    // Function to convert array to string for printing
    public static String arrayToString(int[] arr) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

输出

 
Arranged Array 1: [6, 1, 8, 3, 12, 5]
Arranged Array 2: [4, 7, 10, 9, 14, 13, 18, 19, 20, 21]

时间复杂度

初始步骤包括对数组进行排序，使用 Arrays.sort 方法的时间复杂度为 O(nlogn)。排序后，我们遍历数组一次以将元素放置到正确的位置，时间复杂度为 O(n)。此方法的总时间复杂度为 O(nlogn)。

空间复杂度

我们创建了一个与输入数组长度相同的新数组 arrangedArr 来存储重新排列的元素，这需要 O(n) 的空间。排序算法通常需要额外的空间。例如，如果使用归并排序，它需要 O(n) 的辅助空间。该方法的总空间复杂度为 O(n)。

应用

数据组织
内存布局优化：当数据具有特定模式时，例如交替的偶数和奇数，对其进行组织可以改善内存访问模式，从而提高内存使用效率和计算速度。数据库管理：某些数据库查询或存储模式可能需要将数据以特定方式组织以优化检索和存储过程。
网络
数据包调度：网络数据包可以安排一个模式，其中偶数数据包比奇数数据包具有更高的优先级或不同的路由。这可以用于负载均衡和保证服务质量（QoS）。错误检测和纠正：在通信系统中，以特定模式组织数据可用于更有效地检测和纠正错误。
游戏和模拟
游戏开发：在游戏开发中，以特定顺序组织实体（如玩家或对象）可以优化渲染和碰撞检测过程。模拟：在需要交替更新的模拟中，例如细胞自动机，结构化的顺序可以提高模拟的效率和准确性。

下一个主题Linkedtransferqueue-retainall-method-in-java-with-examples

Java 中偶数索引处的偶数和奇数索引处的奇数

方法一：双指针法

算法

时间复杂度

空间复杂度

方法二：直接交换法

算法

时间复杂度

空间复杂度

方法三：额外空间法

算法

时间复杂度

空间复杂度

方法四：排序法

算法

时间复杂度

空间复杂度

应用

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中偶数索引处的偶数和奇数索引处的奇数

方法一：双指针法

算法

时间复杂度

空间复杂度

方法二：直接交换法

算法

时间复杂度

空间复杂度

方法三：额外空间法

算法

时间复杂度

空间复杂度

方法四：排序法

算法

时间复杂度

空间复杂度

应用

相关帖子

Java 中拆分两个字符串以构成回文

Java Program to Find the Total Number of Ways of Choosing X Men and Y Women from a Total of M Men and W Women

Java 中的内存映射文件是什么

Bell Number in Java

Backwards Compatibility in a Software System with Systematic Reference to Java

Java String Max Size

Java 中每个查询的最大 XOR 值

Java SortedSet E Interface

Java SFTP

Java 中的心形图案

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器