Array easy Start!

(1)448. Find All Numbers Disappeared in an Array

太久不写程序，果真是只废狗了!感觉自己都不会思考了，可怕！Change！！！

本题要注意要求时间复杂度是o(n),空间复杂度为o(1)！【补充时间复杂度和空间复杂度知识】

实在是太生疏，直接寻求最优解如下：

 1 public class Solution {
 2     public List<Integer> findDisappearedNumbers(int[] nums) {
 3         for (int i = 0; i < nums.length; i++){
 4             int val = Math.abs(nums[i]) - 1;
 5             nums[val] = -(Math.abs(nums[val]));
 6         }
 7         List<Integer> arrayList = new ArrayList<>();
 8         for (int i = 0; i < nums.length; i++){
 9             if (nums[i] > 0){
10                 arrayList.add(i + 1);
11             }
12         }
13         return arrayList;
14     }
15 }

View Code

疑问： nums[val] = -(Math.abs(nums[val]));运行正确

nums[val] = -nums[val];运行错误 区别在哪里？？？负负得正啊！！！出现偶次数就不对了。

解题思路：

标志位方法：

把原数组中出现的数其应该所在的位置上置为负值，然后重新遍历如果大于0，则表示从未出现过

正负号标记法：
遍历数组 nums，记当前元素为n，令 nums[abs(n) - 1] = -abs(nums[abs(n) - 1])
再次遍历 nums，将正数对应的下标 +1 返回即为答案，因为正数对应的元素没有被上一步骤标记过。

(2)Move Zeroes

要点注意：1.不能创建新的数组。2.操作总数要最小化。

依然还是直接寻找最优解如下：

 1 public class Solution {
 2     /**
 3      * @param nums an integer array
 4      * @return nothing, do this in-place
 5      */
 6     public void moveZeroes(int[] nums) {
 7         // Write your code here
 8         int zeroIndex = 0;
 9         int noZeroIndex = 0;
10         int n = nums.length;
11         while (zeroIndex < n && noZeroIndex < n){
12             while (zeroIndex < n && nums[zeroIndex] != 0){
13                 zeroIndex++;
14             }
15             while (noZeroIndex < n && (nums[noZeroIndex] == 0 || noZeroIndex < zeroIndex)){
16                 noZeroIndex++;
17             }
18             if (zeroIndex < n && noZeroIndex < n){
19                 nums[zeroIndex++] = nums[noZeroIndex];
20                 nums[noZeroIndex++] = 0;
21             }
22         }
23     }
24 }

View Code

解题思路：

使用两个指针，一个指向0，一个指向非0，二者分别向后遍历，当出现一对（0，非0）时，交换二者位置。

【（非0,0）不需要交换位置，所以条件中出现nonZeroIndex < zeroIndex，此时非0指针加一，不交换位置】

当遍历结束时，0也就被移动到了最后。因为每个节点最多被访问两次，所以时间复杂度为O(n).