当前位置：首页 > news >正文

删除排序数组中的重复项Remove Duplicates from Sorted Array

news 来源：原创 2024/5/6 13:27:41

删除排序数组中的重复项Remove Duplicates from Sorted Array

Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.

Example 1:

Given 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 returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        // 使用双指针
        if(nums==null || nums.length == 1){
            return nums.length;
        }
        int i = 0,j =1;
        while(j<nums.length){
            if(nums[i]==nums[j]){
                j++;
            }else{
                i++;
                nums[i]=nums[j];
                j++;
            }
        }
        return i+1;
    }
}

分析

可以设置两个指针，慢指针i,快指针j。

第一步

数相等,j++

i	j
0	1	2	3	4
1	1	1	2	3

第二步

数相等,j++

i		j
0	1	2	3	4
1	1	1	2	3

第三步

数不等

i			j
0	1	2	3	4
1	1	1	2	3

先i++

	i		j
0	1	2	3	4
1	1	1	2	3

移动nums[i]=nums[j]

	i		j
0	1	2	3	4
1	1	1	2	3
	2

j++

	i			j
0	1	2	3	4
1	1	1	2	3
	2

第四步

这个时候，可以看到数不等

	i			j
0	1	2	3	4
1	1	1	2	3
	2

还是那三步。
先i++

		i		j
0	1	2	3	4
1	1	1	2	3
	2

移动nums[i]=nums[j]

		i		j
0	1	2	3	4
1	1	1	2	3
	2	3

j++

		i
0	1	2	3	4
1	1	1	2	3
	2	3

第五步

这个时候循环条件while(j<nums.length)不满足，j>length，跳出循环，
返回i+1。

完整代码

package remove_duplicates_from_sorted_array;

public class Solution {
	
	//删除排序数组中的重复项
	public int removeDuplicates(int[] nums) {
	    if (nums.length == 0) return 0;
	    int i = 0;
	    for (int j = 1; j < nums.length; j++) {
	        if (nums[j] != nums[i]) {
	            i++;
	            nums[i] = nums[j];
	        }
	    }
	    return i + 1;
	}
	
	//打印数组
	private static void printArry(int len,int[] nums) {
		System.out.println();
		String ss = "[";
		for (int i = 0; i < len; i++) {
			if(i+1==len) {
				ss+=nums[i];
			}else {
				ss+=nums[i]+",";
			}
		}
		ss+="]";
		System.out.println(ss);
	}
	
	public static void main(String[] args) {
		int[] nums = {1,1,2};
		Solution solu = new Solution();
		printArry(nums.length,nums);
		int len = solu.removeDuplicates(nums);
		printArry(len,nums);
	}
	
}