2022年7月5日 星期二

283. Move Zeroes

給定一個整數數組nums,將所有的0移到它的末尾,同時保持非零元素的相對順序。

https://leetcode.com/problems/move-zeroes/

必須在不復制數列的情況下就地執行此操作。

範例
nums = [0,1,0,3,12]
return [1,3,12,0,0]

我們往右遍歷整個數列時,只要注意一件事,記下最靠左的 0 位置,當碰到非 0 的數時,和我們記下的 0 交換位子即可。

因此設定一個從 0 開始的計數器 j,用for迴圈遍歷nums時,只要碰到非 0 的數就和nums[j]交換,此時因nums[j]已經不為0了,因此 j 要尋找下一個 0 的位子,再+1即可。

如果碰到 0 的話 j 就不動,確保 j 鎖定的是最左側的 0 。

還會碰到一種特殊情況,就是數列開頭不為 0 ,但這時因為nums[j]就等於nums[0],所以自己和自己交換後數列根本沒異動。結果就是 j 依然會+1,直到遇到數列中第一個 0 為止。


	public void moveZeroes(int[] nums) {

		int count = nums.length;
		int j = 0;

		for (int i = 0; i < count; i++) {
			if (nums[i] != 0) {
				int tmp = nums[j];
				nums[j] = nums[i];
				nums[i] = tmp;
				j++;
			}
		}
	}

沒有留言:

張貼留言