按着特定条件对数组重排

algorithm
作业部落地址:https://www.zybuluo.com/LIUHUAN/note/383677

1.无序数组中删除目标元素

1.1题目

• Given an array and a value, remove all instances of that value in place and return the new length.
  Do not allocate extra space for another array, you must do this in place with constant memory.
  The order of elements can be changed. It doesn't matter what you leave beyond the new length.
• Example:
  Given input array nums = [3,2,2,3], val = 3
  Your function should return length = 2, with the first two elements of nums being 2.
  Hint:
  Try two pointers.
  Did you use the property of "the order of elements can be changed"?
  What happens when the elements to remove are rare?

1.2题目来源leetcode:Remove Element

1.3思想来源：

• 插入排序

1.4题目分析

• 这个题目比较简单，假设还有一个辅助的数组可以用来存储不等于目标元素的值，那么可以使用两个变量$i$,$start$，一个($i$)记录遍历的元素的位置，另一个($start$)表示将不同于目标值的元素，存放在另一个数组的位置。只要遍历到的元素和目标元素不一样，我们就把这个元素放到start数组指的辅助数组当中，一直遍历到数组末尾。
• 上面的这个方法，需要使用一个辅助数组而且还需要在遍历结束之后把辅助数组里面的内容复制到，原来的数组当中，需要额外的空间和时间。
• 其实我们看下，可以把辅助数组的作用可以使用原来数组来实现，最终删除元素之后的元素个数不会超过原来的数组大小，而且，这个问题具有后效性，就是指针$i$所指的元素前面的元素对后续元素是没有什么影响的。类似于插入排序的思想，遍历到的元素，只要不等于目标元素之后，就可以把着个 元素插入到$start$所指已经“排序好”的元素。只是插入的位置，不在需要一个个和前面已经“排序好”的部分数组进行比较并移动位置，直接插入到$start$之后即可。这里“已排序好”的含义就是这个“部分排序好”的数组里面没有和目标值相等的元素。

1.5代码

 int removeElement(vector<int>& nums, int val) {
        int start = 0;
        for(int i =0;i<nums.size();++i){
            if(nums[i] != val){
                    nums[start++] = nums[i];
            }
        }
        return start;
    }

2.有序数组中删除目标元素

2.1题目

• Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
  Do not allocate extra space for another array, you must do this in place with constant memory.
• For example,
  Given input array nums = [1,1,2],
  Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

2.2题目来源

2.3思想来源

• 插入排序

2.4题目分析

• 这个题目目的是删除一个有序数组里面重复的元素。类似于实现stl里面的unique函数，因为已经有序的数组。思路和上面删除特定元素类似，只是删除的条件变了，这里的删除是，看这个元素和“前面部分有序的数组”的最后一个元素是否相等，如果不想等，那么就把这个元素插入到前面的“有序数组”当中的末尾位置，否则，继续向下扫描剩下的元素。

2.5参考代码

int removeDuplicates(vector<int>& nums) {
        if(nums.empty())
            return 0;
       int start = 0;
       for(int i=1;i<nums.size();++i){
           if(nums[i] !=  nums[start]){
                    nums[++start] = nums[i];
           }
       }
       return start+1;//[0,start]
    }

3.移动数组中0到数组末尾并保持原来相对位置

3.1题目

• Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
• For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
• Note:
  You must do this in-place without making a copy of the array.
  Minimize the total number of operations.

3.2题目来源

• leetcode:Move Zeroes
  

3.3思想来源

• 插入排序，快速排序

3.4题目分析

• 题目的目的是把所有等于0的元素都放到数组的末尾，而非零的元素往前移动并且相对顺序不能改变。类似于稳定的排序要求。
• 从前面的两个题目当中我们可以看出来这个题和前面的题目非常类似，第一个题是删除特定的元素，我们当时只是覆盖了那些等于这个特定元素，并没有把等于这个特定元素的值，移动到数组的末尾。所以这里我们只要在遇到那些不等于0的元素和前面的位置上等于0的元素交换就可以把0交换到末尾来。把覆盖换成交换就可以完成这个题目。但是这样做会有个一问题，并不是交换后的元素一步到位，放在最后为0的位置上，可能还需要在和后面没有扫描的不等于0的元素继续进行交换。
• 这里我们可以想到如果我们按着元素0把作为一个快速排序当中的pivot那么就需要把整个数组的元素按着这个pivot分成两部分，一部分等于pivot一部分不等于pivot。

3.5参考代码

void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int index = 0;
        for(int i=0;i<n;++i){
            if(nums[i] !=0 ){
                swap(nums[i],nums[index++]);
            }
        }
    }

void moveZeroes(vector<int>& nums) {
        int index = 0;
        for(int i=0;i<nums.size();++i){
            if(nums[i] != 0){
                nums[index++] = nums[i];
                if(i+1 != index){
                    nums[i] = 0;
                }
            }
        }
    }

x.有序数组中删除目标元素

x.1题目

x.2题目来源

x.3思想来源

• 插入排序

x.4题目分析

x.5参考代码