《剑指Offer》--- 数据结构の数组篇Ⅱ

面试题21：调整数组顺序使奇数位于偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

在不考虑时间复杂度的条件下，最简单的思路是遍历整个数组，每碰到一个偶数，拿出这个数，并把位于这个数字后面的所有数字往前挪一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。时间复杂度O(n^2)。

新思路：由题目可知，最后所有的奇数都在偶数前面，也就是说，我们在扫描这个数组的时候，如果发现有偶数出现在奇数前面，则交换它们的顺序，交换之后就符合了。

因此，我们可以维护两个指针: 第一个指针初始化时指向数组的第一个数字，它只向后移动;第二个指针初始化时指向数组的最后个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换这两个数字。

    public static int[] Reorder(int[] nums){
        if(nums == null){
            return null;
        }
        if(nums.length == 1){
            return nums;
        }
        int i = 0, j = nums.length - 1;
        for(int x = 0;x < nums.length - 1;x++){
            while(i < j){
                if(nums[i] % 2 == 0 && nums[j] % 2 != 0){
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                    i++;
                    j--;
                } else if(nums[i] % 2 == 0 && nums[j] % 2 == 0){
                    j--;
                } else if(nums[i] % 2 != 0 && nums[j] % 2 != 0){
                    i++;
                } else if(nums[i] % 2 != 0 && nums[j] % 2 == 0){
                    i++;
                    j--;
                }
            }
        }
        return nums;
    }

代码优化：

public static int[] exchange(int[] nums) {
    int i = 0, j = nums.length - 1, tmp;
    while(i < j) {
        while(i < j && (nums[i] & 1) == 1) i++;
        while(i < j && (nums[j] & 1) == 0) j--;
        tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    return nums;
}

面试题39：数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如，输入一个长度位9的数组（1，2，3，2，2，2，5，4，2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

方法一：

数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个数字。

    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

方法二：

我们知道出现次数最多的元素大于 n / 2 次，所以可以用哈希表来快速统计每个元素出现的次数。

    private static Map<Integer,Integer> countNums(int[] nums){
        Map<Integer,Integer> counts = new HashMap<Integer, Integer>();
        for(int num : nums){
            if(!counts.containsKey(num)){
                counts.put(num,1);
            } else {
                counts.put(num,counts.get(num) + 1);
            }
        }
        return counts;
    }