本题为百度质量部面试题
2n个数,一半奇数,一半偶数,设计一个程序让奇数位上的数是奇数,偶数位上的是偶数,并计算程序的空间复杂度和时间复杂度
程序思想:
本题类似于调整数组使奇数位于数组前半部分,偶数位于数组后半部分。
设两个指针,一个初始化为ou=0,另一个初始化为ji=1,如果arr[ou]为偶数,ou+=2;如果arr[ji]为奇数,ji+=2;
如果ou<len && ji<len ,再判断如果偶数为为奇数并且奇数位为偶数,则交换元素。
- public class jiou {
- public static void main(String[] args) {
- int[] arr = { 0, 1, 3, 2, 2, 4, 4, 5, 5,7 };
- reorder(arr);
- for (int i = 0; i < arr.length; i++) {
- System.out.print(arr[i] + ",");
- }
- }
- public static void reorder(int[] arr) {
- if (arr == null) {
- System.out.println("the array is null");
- return;
- }
- int len = arr.length;
- int ou = 0;
- int ji = 1;
- while (ou < len && ji < len) {
- if (arr[ou] % 2 == 0) {
- ou = ou + 2;
- }
- if (arr[ji] % 2 == 1) {
- ji = ji + 2;
- }
- if (ou < len && ji < len) {//该条件的目的是先判断数组下标是否出界,如果不加该条件判断,程序可能会有数组下标越界错误
- if (arr[ou] % 2 == 1 && arr[ji] % 2 == 0) {
- int temp = arr[ou];
- arr[ou] = arr[ji];
- arr[ji] = temp;
- }
- }
- }
- }
- }
程序结果
0,1,2,3,2,5,4,5,4,7,