LeetCode26——删除有序数组中的重复项

序数组中的重复项"/>

LeetCode26——删除有序数组中的重复项

LeetCode26——删除有序数组中的重复项

自己的暴力解（假设可以使用额外的空间）：

时间复杂度：O(N)
空间复杂度：O(N)

package keepcoding.leetcode.leetcode26;
/*给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。*/
public class Result01 {public static void main(String[] args) {int[] arr1 = {1,2,2,3,3,3,4,4};int[] arr2 = {1,1,1,2,2,3,3,3,4,5,5,6,6,6,9,9,9};int[] arr3 = {1,1,2};removeDuplicates(arr1);System.out.println("==================================");removeDuplicates(arr2);System.out.println("==================================");removeDuplicates(arr3);}//暴力解（假设可以使用额外空间）public static void removeDuplicates(int[] arr){//根据传入数组的长度创建新的数组int[] temp = new int[arr.length];//计算temp数组中有效元素的个数int count = 0;//temp数组的下标，方便目标数组的元素存入tempint index = 0;for (int i = 0; i < arr.length-1; i++) {if (arr[i]!=arr[i+1]){//满足条件（不重复）的目标数组的元素存入temp数组temp[index] = arr[i];index++;count++;}}//上述for循环因为i+1数组下标越界问题，无法处理最后一个元素，这里手动将数组最后一个元素加入temp中//因为上述for循环必定已经将除了最后一个元素之前的所有满足条件的元素存入temp中，所以无论最后一个元素重复与否，都应存入最后一个位置的元素temp[index] = arr[arr.length-1];count++;printArray(temp);System.out.println(count);}public static void printArray(int[] arr){//打印数组for (int i = 0; i < arr.length; i++) {if (i==0){if(arr.length==1){System.out.println("["+arr[0]+"]");}else {System.out.print("["+arr[i]);}}else if(i==arr.length-1){System.out.println(","+arr[i]+"]");}else {System.out.print(","+arr[i]);}}}}
时间复杂度：O(N)
空间复杂度：O(1)

官方的解较为巧妙（双指针）：

 public static int removeDuplicates(int[] nums) {int n = nums.length;//如果数组 nums的长度为0，则数组不包含任何元素，因此返回 0。if (n == 0) {return 0;}//双指针/*当数组 nums的长度大于 0 时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此 nums[0]\保持原状即可，从下标 1 开始删除重复元素。定义两个指针 fast 和 slow分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1。*/int fast = 1, slow = 1;while (fast < n) {if (nums[fast] != nums[fast - 1]) {nums[slow] = nums[fast];++slow;}++fast;}return slow;}}