題目大意
給定一個(gè)數(shù)組 nums闷供，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾驹闰，同時(shí)保持非零元素的相對順序。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明：
1.必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。
2.盡量減少操作次數(shù)喷舀。
方法一
從數(shù)組的第0個(gè)元素從頭查找，當(dāng)遇到0時(shí)(如nums[i])淋肾，就查找往后的第一個(gè)非零元素nums[j],然后交換這兩個(gè)元素硫麻。這樣做的時(shí)間復(fù)雜度為O(n^2)。
public void moveZeroes(int[] nums) {
for(int i=0;i<nums.length;i++)
{
if(nums[i]==0)
{
int replace = find_replace_pos(nums,i);
if(replace==i) return;
int temp = nums[i];
nums[i] = nums[replace];
nums[replace] = temp;
}
}
}
private int find_replace_pos(int[] nums,int start) {
for(int j=start+1;j<nums.length;j++)
if(nums[j]!=0) return j;
return start;
}
運(yùn)行時(shí)間41ms,擊敗11.48%樊卓。
方法二：快慢指針
設(shè)置i,j兩個(gè)指針拿愧，當(dāng)j遇到0時(shí)，持續(xù)向后移動(dòng)碌尔。當(dāng)i遇到0時(shí)浇辜，停止移動(dòng)。
public void moveZeroes(int[] nums) {
for(int i=0,j=0;j<nums.length;) { //第一個(gè)0元素
while(i<nums.length && nums[i]!=0) {
++i;
++j;
}
while(j<nums.length && nums[j]==0) ++j;
if(i>=nums.length || j>=nums.length) break;
int temp = nums[i];
nums[i] = nums[j];
nums[j] =temp;
}
}
運(yùn)行時(shí)間2ms,擊敗29.63%唾戚。
方法三：count移位
維護(hù)一個(gè)count變量柳洋，記錄當(dāng)前發(fā)現(xiàn)0的次數(shù)，然后依次將num[i]向前移動(dòng)到相應(yīng)的位置颈走。
public void moveZeroes(int[] nums) {
int cnt = 0;
for(int i=0;i<nums.length;i++)
{
if(nums[i]==0) ++cnt;
else nums[i-cnt] = nums[i];
}
for(int i=nums.length-cnt;i<nums.length;i++)
nums[i]=0;
}
運(yùn)行時(shí)間1ms,擊敗96.97%膳灶。
