关于数据结构与算法:顺序表经典面试题数组的反转找数组中重复的元素使奇数位于偶数前面

56次阅读

共计 2049 个字符，预计需要花费 6 分钟才能阅读完成。

实现计划一

引入一个内部数组变量，用于保留反序之后的数组，而后把原数组中的元素倒序保留于新创建的数组中，新建数组保留的元素就是反转之后的后果

public static void main(String[] args) {int[] arr = {11,22,33,44,55,66,77};
    int[] newArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {newArr[i] = arr[arr.length - 1 - i];
    }
    System.out.println(Arrays.toString(newArr));
}

实现计划二

间接对数组中的元素进行首尾替换。这样防止了新建一个数组来保留反转之后的后果，并且循环遍历的次数也降为计划一的一半，进步了算法的效率

public static void main(String[] args) {int[] arr = {11,22,33,44,55,66,77};
//        int[] newArr = new int[arr.length];
        for (int i = 0; i < arr.length / 2; i++) {//            newArr[i] = arr[arr.length - 1 - i];
            int temp = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }

题目形容

在一个长度为 n 的数组里的所有元素都在 [0,n-1] 范畴内。数组中某些元素是反复的，但不晓得有几个元素是反复的，也不晓得每个元素反复了几次。请找出数组中任意一个反复的元素。例如，如果输出长度为 6 的数组{0,2,4,1,4,3}，那么输入反复的元素 4。

留神：数据不非法或者找不到反复数据的状况，则输入 - 1 即可。

思路剖析

从头到尾顺次扫描数组中的每个元素。当扫描到第 i 个元素的时候，比拟改地位数值 m 是否等于 i。若是，接着扫描下一个元素。否则，将其与第 m 个元素进行比拟。若相等，则返回该反复元素。否则，替换两个元素，持续反复后面的过程。

如果数组元素不反复，则每个元素和对应地位的索引值必定相等，而咱们要做的就是：<u>把数组元素放在正确的地位上。</u>

代码实现

public static void main(String[] args) {int[] arr = {0,9,4,1,4,3};
    int repeatNumber = getRepeatNumber(arr);
    System.out.println(repeatNumber);
}
public static int getRepeatNumber(int[] arr){if (arr == null || arr.length == 0) return -1;
    for (int i = 0; i < arr.length;) {if (arr[i] < 0 || arr[i] >= arr.length) return -1;
        // 数值 m 等于 i，接着扫描下一个元素
        if (arr[i] == i) i++;
        else {
            // 数值 m 与第 m 个元素比拟，如果相等则返回该反复元素
            if (arr[i] == arr[arr[i]]) return arr[i];
            // 把数组元素放在正确的地位上
            else {int temp = arr[i];
                arr[i] = arr[arr[i]];
                arr[temp] = temp;
            }
        }
    }
    return -1;
}

题目形容

输出一个整型数组，实现一个办法来调整数组中元素的程序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半局部。

思路剖析

题目要求所有奇数都应该在偶数后面，所以咱们应该只须要保护两个下标值，让一个下标值从前往后遍历，另外一个下标值从后往前遍历，当发现第一个下标值对应到偶数，第二个下标值对应到奇数的时候，咱们就间接对调两个值。直到第一个下标到了第二个下标前面的时候退出循环。

代码实现

public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9};
    replaceOrderArray(arr);
    System.out.println(Arrays.toString(arr));
}
public static void replaceOrderArray(int[] arr){
    //min 从前往后，max 从后往前
    int min = 0;
    int max = arr.length - 1;
    while (min < max){
        //min 遇到偶数时跳出循环，max 遇到奇数时跳出循环
        while (min < max && arr[min] % 2 != 0) min++;
        while (min < max && arr[max] % 2 == 0) max--;
        // 替换奇数和偶数地位
        if (min != max){int temp = arr[min];
            arr[min] = arr[max];
            arr[max] = temp;
        }
    }
}

正文完