`

Facebook interview - Move all zeroes to end of array

 
阅读更多

Given an array of random numbers, Push all the zero’s of a given array to the end of the array. For example, if the given arrays is {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, it should be changed to {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}. The order of all other elements should be same. Expected time complexity is O(n) and extra space is O(1).

 

Solution 1:

It rerains ordering.

// move all zeros to end of array, keep the non-zero elements order
public static void moveZeroToEnd(int[] A) {
	int n = A.length, cnt = 0;
	for(int i=0; i<n; i++) {
		if(A[i] != 0) {
			A[cnt++] = A[i];
		}
	}
	while(cnt < n) {
		A[cnt++] = 0;
	}
}

 

Solution 2:

It does not keep the non-zero elements order.

// move all zeros to end of array, does not keep the non-zero elements order
public static void moveZeroRight(int[] A) {
	for(int i=0, j=A.length-1; i<j; i++) {
		if(A[i] == 0) {
			while(j>i && A[j] == 0) j--;
			swap(A, i, j);
		}
	}
}

private static void swap(int[] A, int i, int j) {
	int tmp = A[i];
	A[i] = A[j];
	A[j] = tmp;
}

 

分享到:
评论

相关推荐

    LeetCode最全代码

    Here is the classification of all `468` questions. For more questions and solutions, you can see my [LintCode](https://github.com/kamyu104/LintCode) repository. I'll keep updating for full summary and...

    letscode:LeetCode

    1.MoveZeroes |-- codedrinker |-- MoveZeroes.java 访问官网,注册账号 访问每个译文下面的Readme.md里面是链接地址和译文 完成编码以后,到LeetCode官网提交结果,接受以后再提交Pull Request合并到master

    leetcode刷题账号-leetcode:leetcode

    1.MoveZeroes |-- codedrinker |-- MoveZeroes.java 访问 官网,注册账号 编码完成以后,在LeetCode官网运行结果通过以后再提交代码到我们的仓库。 如果不理解 Git 怎么使用可以观看这个视频 加群 QQ 免费 607313352...

    cpp-算法精粹

    Substring with Concatenation of All Words Pascal's Triangle Pascal's Triangle II Spiral Matrix Spiral Matrix II ZigZag Conversion Divide Two Integers Text Justification Max Points on a Line Community ...

    eac3to V3.17

    * fixed: WAV files beginning with lots of zeroes were sometimes not accepted v3.14 * WAV reading was broken for all but very small files (introduced in v3.13) v3.13 * fields and frames are counted ...

    sigfigstr - 使用适当数量的 sigfigs 打印:此功能旨在创建具有适当数量的有效数字(无论大小)的格式化数字字符串。-matlab开发

    它受到堆栈溢出工作的启发( https://stackoverflow.com/questions/21354701/matlab-fprintf-to-keep-重要数字-and-rightmost- zeroes )。 这是它在行动中的一个例子&gt;&gt; sigfigstr(.000012431634,3) ans = '0....

    MySQL.and.Perl.for.the.Web

    This tutorial is an excellent way for Perl developers to move to the next level of development and make the most of some powerful, free tools. --Stephen W. Plain Product Description MySQL and Perl ...

    Windows 7 Administrator’s Pocket Consultant.pdf

    Toward that end, the book covers everything you need to perform the core administrative tasks for computers running Windows 7. Because my focus is on giving you maximum value in a pocket-size guide,...

    leetcode提交记录消失-leetcode-java:我对leetcode问题的解决方案

    leetcode提交记录消失解决leetcode问题 ...https://leetcode.com/problems/roman-to-integer/description/ first-submission-successful : yes 2018-05-16 : - id : 172 type : math difficulty : easy url : ...

    recommended-problems

    这是我准备面试时建议的个人问题清单。 图表 数组 散列 链表 ... ... https://leetcode.com/problems/set-matrix-zeroes/ ...https://leetcode.com/problems/positions-of-large-g

    【英语】高考英语语法复习结构图解.doc

    两者皆可 zero-zeros/zeroes, volcano-volcanoes/ volcanos 7 以元音字母加-o结尾的名词加-s radio-radios, bamboo-bamboos, zoo-zoos 8 以-th结尾的名词加-s truth-truths, mouth-mouths, month-months, path-...

    Leetcode的ac是什么意思-LeetCodeInJava:leetcode-java

    to Buy and Sell Stock II #136 Single Number #150 Evaluate Reverse Polish Notation #169 Majority Element #171 Excel Sheet Column Number #217 Contains Duplicate #226 Invert Binary Tree #237 Delete Node ...

    收集面试中提出的一些重要问题。-C/C++开发

    数组https://leetcode.com/problems/3sum/ [解决方案] https://leetcode.com/problems/trapping-rain-water/ [解决方案] https://leetcode.com/problems/move-zeroes/ https ://leetcode.com/problems/best-time-to-...

    node-zeroes:创建填充0的数组的工具

    0秒 一个简单的工具来创建一个只有0的数组 ...var zeroes = require("0s"); 然后输入所需的数组长度 zeroes() // [] zeroes(0) // [] zeroes(1) // [1] zeroes(5) // [1, 1, 1, 1, 1] 版本号 1.0.0第一版

    lrucacheleetcode-LeetCode_30Day:力扣30天挑战赛

    Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ANAGRAMS 7 COUNTING ELEMENTS 日 问题描述 问题和解决方案链接 Git 解决方案页面 8 Middle of the Linked List 9 Backspace String Compare 10 Min Stack 11 ...

    amcharts中文教程(柱状图,饼状图等的中文设置说明)

    -- 设置所有文本的大小,默认为11,具体的文本的字体大小也可以在下面的设置中设置[11] (Number) text size of all texts. Every text size can be set individually in the settings below --&gt; &lt;text_color&gt;&lt;/...

    Wrox.Professional.Mobile.Application.Development.2012

    Creating applications for the myriad versions and varieties of mobile phone platforms on the market can be daunting to even the most seasoned developer. This authoritative guide is written in such as ...

    lrucacheleetcode-leetcode:记录自己的leetcode解题历程~Welcomeeveryonetocomment:grinning_face:~

    Zeroes 48. Rotate Image 344. Reverse String 414. Third Maximum Number 448. Find All Numbers Disappeared in an Array 66. Plus One 238. Product of Array Except Self 697. Degree of an Array 849. ...

    zeroes-crx插件

    语言:English 查找任何二次函数的零。 简单的。 一个简单的chrome扩展名,可帮助您在浏览器中找到二次方程的x截距。 有助于进行数学测试,或者只是在您喜欢那些甜美的零甜食时!

Global site tag (gtag.js) - Google Analytics