奇下标奇值 偶下标偶值

算法

Posted by CH on May 27, 2020

题目

给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。

对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

(时间复杂度不能超过N^2)

示例

输入[4,2,5,7]
输出[4,5,2,7]
解释[4,7,2,5][2,5,4,7][2,7,4,5] 也会被接受

题干

A 中一半整数是奇数,一半整数是偶数

A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。 也就是 奇下标奇值 偶下标偶值

有什么特点 - 不符合条件的数一定是成对出现的

重点在于 不符合条件的值之间如何交换 满足条件

思路

咋一看这题 暴力解法是肯定可以解的

首先循环数组 一个个找出不符合条件的 找到之后 循环剩下的直到也找到不符合条件的进行交换 直到循环结束

这样的时间复杂度在N^2 是不符合条件的

所以我们要利用空间 特性来解题

空间解法

循环数组 不符合条件的值取出

偶数一个数组 奇数一个数组 原数组= -1

再循环找到-1 根据下标的奇偶性 从数组中取1赋值 直到结束

双指针算法

指针i 指向偶数位 指针j 指向位奇数

while循环 i每次进2 如果找到不符合的停止 让j进2

两个都找到之后交换 直到循环结束

解答

空间解法

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        List<Integer> odds = new ArrayList();
        List<Integer> evens = new ArrayList();
        for(int i=0;i<nums.length;i++){
            int value = nums[i];
            if(!isSame(i,value)){
                nums[i] = -1;
                if(isOdd(value)){
                    odds.add(value);
                }else {
                    evens.add(value);
                }
            }
        }
       
        int oddIndex = 0;
        int evenIndex = 0;
        for(int i=0;i<nums.length;i++){
            int value = nums[i];
            if(value == -1){
                if(isOdd(i)){
                    int lastElement = odds.get(oddIndex);
                    nums[i] = lastElement;
                    oddIndex++;
                }else {
                    int lastElement = evens.get(evenIndex);
                    nums[i] =lastElement;
                    evenIndex++;
                }
            }
        }
        return nums;
    }

     public static boolean isSame(int i,int value){
        return (isOdd(i)&& isOdd(value))||(!isOdd(i)&&!isOdd(value));
    }

    public static boolean isOdd(int num){
        return num%2!=0;
    }

}

双指针算法

class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int n = A.length;
        int j = 1;
        for (int i = 0; i < n; i += 2) {
            if (A[i] % 2 == 1) {
                while (A[j] % 2 == 1) {
                    j += 2;
                }
                swap(A, i, j);
            }
        }   
        return A;
    }

    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

时空复杂度分析

如果采用空间解法 时间复杂度为O(2n) 空间复杂度为O(2n)

如果采用双指针算法 时间复杂度为O(N) 空间复杂度为O(n)

结语

抓住特性非常重要 并且双指针是解决交换问题的利器 需要牢牢掌握