Leetcode26--->Remove Duplicates from Sorted Array(从排序数组中移除相同的元素)

wtuyss

　　题目： 给定一个排序数组，移除重复出现的元素，保证每个元素最终在数组中只出现一次。返回新数组的长度length; 要求：不能分配额外的一个数组使用，必须使用原地排序的思想，且空间复杂度为O(1)
　　举例：
　　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.
　　解题思路：
　　1. 由于数组本身是有序的，且题目要求使用原地排序，因此结果也肯定是有序的（出去数组末尾的哪些被删除的数据） 1112333
　　2. 采用两个标志位，一个在当前位begin，另一个向后遍历（从begin的下一位开始），直到遇到与当前位不一样的数字，在此之间的所有相同数字，统一置为nums[0],即将与数组中所有第一次出现的数字相同的所有数组都置为0;此时数组变成1112311
　　3. 依然采用两个标志位，start表示除了nums[0]之外的下一个与nums[0]相等的数的位，index表示第一个与nums[0]不相等的数的位，交换彼此；一次交换的结果变为1211311，两次交换的结果为1231111
　　4.  每交换一次，表示有一个不被删除的元素，再加上第一个元素，结果为count + 1;
　　代码如下：



1 public class Solution {
2     public int removeDuplicates(int[] nums) {
3         if(nums == null || nums.length < 1)
4             return 0;
5         int begin = 0;
6         int count = 0;
　　　　　　// 将与数组中所有第一次出现的数字相同的所有数字都置为nums[0]
7         for(int i = 1; i < nums.length; i++){
8             if(nums == nums[begin]){
9                 nums = nums[0];
10                 continue;
11             }
12             begin = i; // 下一个第一次出现的数字
13         }
14         int index = 1;
15         int start = 1;
16         while(index < nums.length){
17             if(nums[index] == nums[0]){  // 找到与nums[0]不相同的那个位
18                 index ++;
19                 continue;
20             }
21             exchange(nums, start, index);  // 交换
22             start ++;
23             count ++;
24             index ++;
25         }
26         return count + 1;  // 最终交换的次数 + 1
27     }
28     public void exchange(int[] nums, int index1, int index2){
29         if(index1 == index2)
30             return;
31         int temp = nums[index1];
32         nums[index1] = nums[index2];
33         nums[index2] = temp;
34     }
35 }