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

题目：给定一个排序数组，移除重复出现的元素，保证每个元素最终在数组中只出现一次。返回新数组的长度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;

代码如下：

 public class Solution {

     public int removeDuplicates(int[] nums) {

         if(nums == null || nums.length < 1)

             return 0;

         int begin = 0;

         int count = 0;
　　　　　　// 将与数组中所有第一次出现的数字相同的所有数字都置为nums[0]

         for(int i = 1; i < nums.length; i++){

             if(nums[i] == nums[begin]){

                 nums[i] = nums[0];

                 continue;

             }

             begin = i; // 下一个第一次出现的数字

         }

         int index = 1;

         int start = 1;

         while(index < nums.length){

             if(nums[index] == nums[0]){  // 找到与nums[0]不相同的那个位

                 index ++;

                 continue;

             }

             exchange(nums, start, index);  // 交换

             start ++;

             count ++;

             index ++;

         }

         return count + 1;  // 最终交换的次数 + 1

     }

     public void exchange(int[] nums, int index1, int index2){

         if(index1 == index2)

             return;

         int temp = nums[index1];

         nums[index1] = nums[index2];

         nums[index2] = temp;

     }

 }

巴特西

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

最新文章

热门文章