Google – Shuffle With Blank
输入一个unsorted array, 其中缺了一个值，比如[0, 2, _, 3], 要求移动数字使得每个数都在对应的index上，但是移动的要求是数字只能移动到空的位置上。
[Solution]
首先这题的题意可能和原题有出入，面经讲的不是很清楚。但是即使就按上面题目的描述来做，code也没有想象中的好写。
其实就是换种方法swap。把每个数字换到对应的index上，除非对应的index正好empty，否则empty位置不变，继续换当前位置的数字（就是本来在index上刚刚换过来的）。
Read full article from Google – Shuffle With Blank
输入一个unsorted array, 其中缺了一个值，比如[0, 2, _, 3], 要求移动数字使得每个数都在对应的index上，但是移动的要求是数字只能移动到空的位置上。
[Solution]
首先这题的题意可能和原题有出入，面经讲的不是很清楚。但是即使就按上面题目的描述来做，code也没有想象中的好写。
其实就是换种方法swap。把每个数字换到对应的index上，除非对应的index正好empty，否则empty位置不变，继续换当前位置的数字（就是本来在index上刚刚换过来的）。
Solution { public void shuffle(int[] nums) { if (nums == null || nums.length == 0) { return; } int emptyIdx = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] == -1) { emptyIdx = i; break; } } shuffle(nums, emptyIdx); } private void shuffle(int[] nums, int emptyIdx) { int i = 0; while (i < nums.length) { if (i != emptyIdx && nums[i] != i && nums[i] < nums.length) { int newEmptyIdx = swap(nums, i, nums[i], emptyIdx); if (emptyIdx != newEmptyIdx) { i++; } emptyIdx = newEmptyIdx; } else { i++; } } } private int swap(int[] nums, int i, int j, int emptyIdx) { if (j == emptyIdx) { nums[j] = nums[i]; nums[i] = -1; return i; } else { nums[emptyIdx] = nums[j]; nums[j] = nums[i]; nums[i] = nums[emptyIdx]; nums[emptyIdx] = -1; return emptyIdx; } }} |
