Leetcode 283 Move Zeroes
【摘要】
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:
必须在...
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数
思路分析之基本套路
- 在不申请新的数组的前提下，遍历一遍数组，而且只使用一个索引变量，是无法求解这个题目。
- 既然无法使用一个索引变量，那我们是否能使用两个索引变量来解决问题呢？是可以的。那我们就想到了使用两个索引变量的经典问题：冒泡排序、选择排序、插入排序这三种思路，看看是否能解决此问题。
冒泡排序的应用
冒泡排序的要点分析
对于n个元素的数组来说，一般分为n-1轮任务。在冒泡排序的每一轮任务中，通过从左往右（是否可以通过从右向左平移呢？）平移的两两元素比较，然后进行交换，达到最大值放到末尾（问题规模减小后的），从而使得每次任务的规模减少，最终达到排序的目的。
冒泡排序的应用1
我们也可以通过相邻元素的判断，进行交换，使得每次的0都放到末尾。具体代码如下所示：
c++版本
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for (int i=0; i<nums.size() - 1; ++i) {
for (int j = 0; j<nums.size() - 1 - i; ++j) {
if (nums[j] == 0 && nums[j+1] != 0) {
swap(nums[j], nums[j+1]);
}
}
}
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
Java版本
class Solution {
public void moveZeroes(int[] nums) {
for(int i=0; i<nums.length; ++i) {
for (int j=0; j<nums.length - i - 1; ++j) {
if (nums[j] == 0 && nums[j + 1] != 0) {
nums[j] = nums[j] ^ nums[j + 1];
nums[j+1] = nums[j] ^ nums[j + 1];
nums[j] = nums[j] ^ nums[j + 1];
}
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
Python版本
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
for i in range(0, len(nums) - 1):
for j in range(0, len(nums) - i - 1):
if nums[j] == 0 and nums[j+1] != 0:
nums[j], nums[j+1] = nums[j+1], nums[j]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
冒泡排序的应用2
如果我们每一轮是从从右向左，而不是从左到右，这样每一轮就会使非0的元素放到了头部。具体代码如下所示：
c++版本
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for (int i=0; i<nums.size(); ++i) {
for(int j=nums.size() - 1; j>=i+1; --j) {
if (nums[j-1] == 0 && nums[j] != 0) {
swap(nums[j-1], nums[j]);
}
}
}
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
Java版本
class Solution {
public void moveZeroes(int[] nums) {
for (int i=0; i<nums.length - 1; ++i) {
for (int j = nums.length - 1; j >= i+1; --j) {
if (nums[j-1] == 0 && nums[j] != 0) {
nums[j - 1] = nums[j] ^ nums[j - 1];
nums[j] = nums[j] ^ nums[j - 1];
nums[j - 1] = nums[j] ^ nums[j - 1];
}
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
Python版本
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
for i in range(0, len(nums) - 1):
for j in range(len(nums) - 1, i , -1):
if (nums[j - 1] == 0 and nums[j] != 0):
nums[j - 1], nums[j] = nums[j], nums[j - 1]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
选择排序的应用
选择排序的要点分析
对于n个元素的数组来说，一般分为n-1轮任务。在选择排序的每一轮任务中，通过遍历得到最小值和最开头（问题规模减小后的）的元素进行交换，然后提前结束该轮任务。
选择排序的应用
我们将每次最开头而且为0的元素和后面的第一个非0的元素进行交换即可，具体代码如下所示：
c++代码
void moveZeroes(vector<int>& nums) {
for (int i=0; i<nums.size()-1; ++i) {
if (nums[i] == 0) {
for(int j=i+1; j<nums.size(); ++j) {
if (nums[j] != 0) {
swap(nums[i], nums[j]);
break;
}
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
Java代码
class Solution {
public void moveZeroes(int[] nums) {
for (int i=0; i<nums.length - 1; ++i) {
if (nums[i] == 0) {
for (int j=i+1; j<nums.length; ++j) {
if (nums[j] != 0) {
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
break;
}
}
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
Python代码
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
for i in range(0, len(nums) - 1):
if nums[i] == 0:
for j in range(i+1, len(nums)):
if nums[j] != 0:
nums[i], nums[j] = nums[j], nums[i]
break
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
插入排序的应用
插入排序的要点分析
对于n个元素的数组来说，一般分为n-1轮任务。在选择排序的每一轮任务中，将元素插入到正确的位置中。如果使用后插法的话，就是从右向左遍历，如果发现比当前元素小的元素，则插入到其后面，并提前结束这一轮循环。否则，边遍历边把元素覆盖到后面的位置。如果一直没有发现比它小的元素，最终插入到最前面。
插入排序的应用
思想类似，把当前元素插入到非0元素的后面：
c++版本
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int i=1; i<nums.size(); ++i) {
int list_value = nums[i];
for(int j=i-1; j>=0; --j) {
if(nums[j] != 0) {
nums[j + 1] = list_value;
break;
}
else{
nums[j + 1] = nums[j];
if (j == 0) {
nums[0] = list_value;
}
}
}
}
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
Java版本
class Solution {
public void moveZeroes(int[] nums) {
for(int i=1; i<nums.length; ++i) {
int list_value = nums[i];
for(int j=i-1; j>=0; --j) {
if (nums[j] != 0) {
nums[j + 1] = list_value;
break;
}
else{
nums[j + 1] = nums[j];
if (j == 0) {
nums[0] = list_value;
}
}
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
Python版本
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
for i in range(1, len(nums)):
list_value = nums[i]
for j in range(i-1, -1, -1):
if nums[j] != 0:
nums[j + 1] = list_value
break
else:
nums[j + 1] = nums[j]
if j == 0:
nums[0] = list_value
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
方法的优化
问题：上述的所有方法的时间复杂度都是o(n^2)，这种的时间复杂度往往是不可用的。那我们是否有更好的解决方法呢？
方法：如果我们把数据分为两部分，非0段和0段。通过一次循环把非0段的值放入到正确的位置，然后把0段的也放到正确的位置就OK了。这样就实现了o(n)的时间复杂度。本质上它是基于插入排序的改进。
C++版本
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = 0;
int insert_pos = 0;
while (i < nums.size()) {
if (nums[i] != 0) {
nums[insert_pos] = nums[i];
insert_pos += 1;
}
++i;
}
while(insert_pos < nums.size()) {
nums[insert_pos] = 0;
insert_pos += 1;
}
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
Java版本
class Solution {
public void moveZeroes(int[] nums) {
int i = 0;
int insert_pos = 0;
while (i < nums.length) {
if (nums[i] != 0) {
nums[insert_pos] = nums[i];
++insert_pos;
}
++i;
}
while(insert_pos < nums.length) {
nums[insert_pos] = 0;
++insert_pos;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
Python版本
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = 0
insert_pos = 0
while i < len(nums):
if nums[i] != 0:
nums[insert_pos] = nums[i]
insert_pos += 1
i += 1
while insert_pos < len(nums):
nums[insert_pos] = 0
insert_pos += 1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
是否有办法把非0元素填充完的时刻，0元素也填充好了呢？
c++版本
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int i = 0;
int insert_pos = 0;
while (i < nums.size()) {
if (nums[i] != 0) {
if (i != insert_pos) {
swap(nums[i], nums[insert_pos]);
}
++insert_pos;
}
++i;
}
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
[0, i] not zero, [i+1, j] zero
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// [0, i] not zero, [i+1, j] zero
int i = -1;
for(int j=0; j<nums.size(); ++j) {
if (nums[j] != 0) {
swap(nums[++i], nums[j]);
}
}
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
文章来源: blog.csdn.net，作者：herosunly，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/herosunly/article/details/86635282
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）