LeetCode 281. Move Zeros

LeetCode in Java (8 Part Series)

1 LeetCode 20. Valid Parentheses
2 LeetCode 7. Reverse Integer
… 4 more parts…
3 LeetCode 281. Move Zeros
4 LeetCode 238. Product of Array Except Self
5 LeetCode 31. Next Permutation
6 LeetCode 98. Validate Binary Search Tree
7 LeetCode 111. Minimum Depth of Binary Tree
8 LeetCode in Java: 209


<span>public</span> <span>void</span> <span>moveZeroes</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>)</span> <span>{</span>
    <span>int</span> <span>count</span> <span>=</span> <span>0</span><span>;</span>
    <span>for</span> <span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>nums</span><span>.</span><span>length</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
        <span>if</span> <span>(</span><span>nums</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
            <span>count</span><span>++;</span>
            <span>continue</span><span>;</span>
        <span>}</span>
        <span>if</span> <span>(</span><span>count</span> <span>></span> <span>0</span><span>)</span> <span>{</span>
            <span>swap</span><span>(</span><span>nums</span><span>,</span> <span>i</span><span>,</span> <span>i</span> <span>-</span> <span>count</span><span>);</span>
        <span>}</span>
    <span>}</span>
<span>}</span>
<span>private</span> <span>void</span> <span>swap</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>,</span> <span>int</span> <span>i</span><span>,</span> <span>int</span> <span>j</span><span>)</span> <span>{</span>
    <span>int</span> <span>temp</span> <span>=</span> <span>nums</span><span>[</span><span>i</span><span>];</span>
    <span>nums</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>nums</span><span>[</span><span>j</span><span>];</span>
    <span>nums</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>temp</span><span>;</span>
<span>}</span>
<span>public</span> <span>void</span> <span>moveZeroes</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>)</span> <span>{</span>
    <span>int</span> <span>count</span> <span>=</span> <span>0</span><span>;</span>

    <span>for</span> <span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span> <span>i</span> <span><</span> <span>nums</span><span>.</span><span>length</span><span>;</span> <span>i</span><span>++)</span> <span>{</span>
        <span>if</span> <span>(</span><span>nums</span><span>[</span><span>i</span><span>]</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
            <span>count</span><span>++;</span>
            <span>continue</span><span>;</span>
        <span>}</span>
        <span>if</span> <span>(</span><span>count</span> <span>></span> <span>0</span><span>)</span> <span>{</span>
            <span>swap</span><span>(</span><span>nums</span><span>,</span> <span>i</span><span>,</span> <span>i</span> <span>-</span> <span>count</span><span>);</span>
        <span>}</span>
    <span>}</span>
<span>}</span>

<span>private</span> <span>void</span> <span>swap</span><span>(</span><span>int</span><span>[]</span> <span>nums</span><span>,</span> <span>int</span> <span>i</span><span>,</span> <span>int</span> <span>j</span><span>)</span> <span>{</span>
    <span>int</span> <span>temp</span> <span>=</span> <span>nums</span><span>[</span><span>i</span><span>];</span>
    <span>nums</span><span>[</span><span>i</span><span>]</span> <span>=</span> <span>nums</span><span>[</span><span>j</span><span>];</span>
    <span>nums</span><span>[</span><span>j</span><span>]</span> <span>=</span> <span>temp</span><span>;</span>
<span>}</span>
public void moveZeroes(int[] nums) {
    int count = 0;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            count++;
            continue;
        }
        if (count > 0) {
            swap(nums, i, i - count);
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

The essence of this approach is to swap a non-zero element with the left-most zero.

We iterate through the array nums and increment count by one when we encounter a zero, i.e. we calculate the distance between the left-most zero and a non-zero element. Once we meet a non-zero element, we swap it with the zero at i - count. At the end of the iteration, the zeros have been moved to the end and the relative positions of non-zero elements remain unchanged.

LeetCode in Java (8 Part Series)

原文链接：LeetCode 281. Move Zeros

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END