leetcode-283.移动零 | LIXI.FUN

LIXI.FUN

做个有趣的人

0%

leetcode-283.移动零

发表于 分类于

题目链接

283.移动零

代码

最终是这个样子的

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void moveZeroes(int[] nums) {

        int notZeroIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && i != ++notZeroIndex) {
                nums[notZeroIndex] = nums[i];
                nums[i] = 0;
            }
        }
    }
}

再看是怎样一步一步过来的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public void moveZeroes(int[] nums) {
        
        // 不为零的元素要占的下标位置
        int notZeroIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // 找到一个非零值就 ++
                ++notZeroIndex;

                if (i == notZeroIndex) {
                    // i 和 notZeroIndex 走的一样快，nums[i] 没有遇到过 0
                    // 两个指向同一个位置，什么也不做
                } else {
                    // i 比 notZeroIndex 走的快，nums[i] 遇到过 0
                    // 此时意味着 notZeroIndex 要占据位置的 元素值 原本为 0，需要用 nums[i] 来代替
                    // 相当于交换了 notZeroIndex 和 i 的位置的 元素值
                    nums[notZeroIndex] = nums[i];
                    nums[i] = 0;
                }
            }
        }
    }
}

简化，去掉 i == notZeroIndex 的空 if 语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void moveZeroes(int[] nums) {
        
        // 不为零的元素要占的位置
        int notZeroIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // 找到一个非零值
                ++notZeroIndex;

                if (i != notZeroIndex) {
                    // i 比 notZeroIndex 走的快，nums[i] 遇到过 0
                    // 此时意味着 notZeroIndex 要占据位置的 元素值 原本为 0，需要用 nums[i] 来代替
                    // 相当于交换了 notZeroIndex 和 i 的位置的 元素值
                    nums[notZeroIndex] = nums[i];
                    nums[i] = 0;
                }
            }
        }
    }
}

++ 可以放到判断条件里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void moveZeroes(int[] nums) {
        
        // 不为零的元素要占的位置
        int notZeroIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (i != ++notZeroIndex) {
                    // i 比 notZeroIndex 走的快，nums[i] 遇到过 0
                    // 此时意味着 notZeroIndex 要占据位置的 元素值 原本为 0，需要用 nums[i] 来代替
                    // 相当于交换了 notZeroIndex 和 i 的位置的 元素值
                    nums[notZeroIndex] = nums[i];
                    nums[i] = 0;
                }
            }
        }
    }
}

短路与，if 条件合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void moveZeroes(int[] nums) {
        
        // 不为零的元素要占的位置
        int notZeroIndex = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && i != ++notZeroIndex) {

                // i 比 notZeroIndex 走的快，nums[i] 遇到过 0
                // 此时意味着 notZeroIndex 要占据位置的 元素值 原本为 0，需要用 nums[i] 来代替
                // 相当于交换了 notZeroIndex 和 i 的位置的 元素值
                nums[notZeroIndex] = nums[i];
                nums[i] = 0;
            }
        }
    }
}

复杂度分析

  • 时间复杂度: O(N)
  • 空间复杂度: O(1)
觉得有收获就鼓励下作者吧