这是悦乐书的第 201 次更新, 第 211 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 67 题 (顺位题号是 283). 给定一个数组 nums, 写一个函数将所有 0 移动到它的末尾, 同时保持非零元素的相对顺序. 例如:
输入:[0,1,0,3,12]
输出:[1,3,12,0,0]
注意:
您必须在不制作数组副本的情况下就地执行此操作.
最小化操作总数.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
借助一个新数组和计数变量 count, 将不为 0 的数先存入新数组, 然后将新数组中前 count 位赋值给数组的对应位, 再将剩下的全赋值为 0 即可.
此解法的时间复杂度是 O(n), 空间复杂度是 O(n).
- public void moveZeroes(int[] nums) {
- if (nums == null || nums.length == 0) {
- return ;
- }
- int[] newnums = new int[nums.length];
- int count = 0;
- for (int i=0; i<nums.length; i++) {
- if (nums[i] != 0) {
- newnums[count] = nums[i];
- count++;
- }
- }
- for (int j=0; j<nums.length; j++) {
- if (j < count) {
- nums[j] = newnums[j];
- } else {
- nums[j] = 0;
- }
- }
- }
03 第二种解法
借用冒泡排序的思路, 如果当前元素不等于 0, 就与前面的元素进行交换, 这其中要借助一个变量指针来帮助我们完成交换的工作.
此解法的时间复杂度是 O(n), 空间复杂度是 O(1).
- public void moveZeroes2(int[] nums) {
- if (nums == null || nums.length == 0) {
- return ;
- }
- int index = 0;
- for(int i=0; i < nums.length; i++) {
- if (nums[i] != 0) {
- int temp = nums[index];
- nums[index] = nums[i];
- nums[i] = temp;
- index++;
- }
- }
- }
04 第三种解法
我们可以先将不等于 0 的元素放到数组的前面, 这需要借助一个局部变量, 一个从 0 开始的指针. 然后再将剩下索引所对应的元素全部赋值为 0.
此解法的时间复杂度是 O(n), 空间复杂度是 O(1).
- public void moveZeroes3(int[] nums) {
- if (nums == null || nums.length == 0) {
- return ;
- }
- int index = 0;
- for (int num : nums) {
- if (num != 0) {
- nums[index++] = num;
- }
- }
- for (int i=index; i<nums.length; i++) {
- nums[i] = 0;
- }
- }
05 小结
算法专题目前已连续日更超过一个月, 算法题文章 67 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/bff96df254a8