[leetcode]RemoveDuplicatedInsortedArray

Search in Rotated Sorted Array 

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.

 

思路一（不好，只是为了记录自己的思路轨迹，可忽略不看）：

循环遍历链表，循环体：

1. 对于每一个A[i]，下标指针j指向i 循环j++直到A[j]不等于A[i]或者到达数组末尾为止。这个时候找到了和A[i]不等的数；

2. 将j以及j之后的值依次挪动到i+1以及之后的位置。

3. i++;

这个思路仔细思考下去是可以的。但是问题就是每次都需要挪动数组，而且每次挪动后都不一定是他们最终的位置，以后还要挪动。还有个问题是循环次数很多。而且长度变化计算起来比较麻烦。

 

 

思路2：

1. 自己的脑子里面维持一个新的逻辑数组（数组里面元素是不重复的）的概念；

2. 定义下标指针 i 永远指向新的逻辑数组的尾部元素；定义下标指针 tail 永远指向这个新数组的尾部元素的下一个。因为第一个元素肯定是不重复的，所以i 初始值为0，tail 初始值为1；

3. 定义下标指针j 指向扫描到的不等于A[i]的元素下标，现在假设我们已经有了一个不重复的数组为下标范围为[0,i]，则下一个位置（tail）处放的值为A[j];

4. 我们在循环过程中维持上述规定不变就可以了。

 

代码如下：

 public int removeDuplicates(int[] A) {
	        // Start typing your Java solution below
	        // DO NOT write main() function
	        if(A == null||A.length == 0) return 0;

	        int i = 0;//永远指向逻辑新数组（存储仍然在原来数组）的尾部
	        int tail = i+1;//永远指向逻辑新数组（存储仍然在原来数组）的尾部的下一位
	        int j = i;
	        
	        while(j<=A.length-1){
	            while(j<=A.length-1&&A[j]==A[i]) j++;
	            //达到数组长度或者找到一个不相等的值时，跳出循环
	            if(j<=A.length-1){
	                A[tail] = A[j];
	                i++;
	                tail++;
	            }
	        }
	        return tail;
	    }

 

Search in Rotated Sorted Array II

 跟上一题的思路是类似的。代码：

 

public int removeDuplicates(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A == null||A.length == 0) return 0;
        int i = 0;
        int j = i;
        int prevj = j;
        int tail = i+1;
        
        int len = A.length;
        
        while(j <= len-1){
            prevj = j;
            while(j<=len-1&&A[j]==A[i]) j++;
            //此时有A[prevj] = A[i]&&A[j]!=A[i]
            if(j>prevj+1){[prevj,j]区间内有等于A[i]的值，只取一个A[j-1]
                A[tail] = A[j-1];
                tail++;
                i++;
                if(j<=len-1) {A[tail]= A[j];tail++;i++;}
            }
            else{//[prevj,j]区间内没有等于A[i]的值，和上题一样
                if(j<=len-1) {A[tail]= A[j];tail++;i++;}
            }
        }
        return tail;
    }

 同样思路解决Remove Duplicates from Sorted List

 

 public ListNode deleteDuplicates(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head == null) return null;
        
        ListNode i = head;
        ListNode j = i;
        ListNode tail = i.next;
        
        while(j!=null){
            while(j!=null&&i.val == j.val) j = j.next;
            if(j!=null){
                tail.val = j.val;
                tail = tail.next;
                i = i.next;
            }
        }
        i.next = null;
        return head;  
    }

 Remove Duplicates from Sorted List II

 public ListNode deleteDuplicates(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head == null) return null;
        
        ListNode j = head;
        ListNode tail = null;//删除后的数组尾,初始为0
        ListNode i = head;
        
        while(j!=null){
            i = j;
            while(j!=null&&i.val == j.val) j = j.next;
            if(j == i.next){//没有和i相同的
                    if(tail == null){head = i; tail = i;}
                    else {tail.next.val = i.val;tail = tail.next;}
            }
            
        }
        if(tail!=null){
            tail.next = null;
            return head;
        }else{
            return null;
        }
    }

测试用例：

tail 为空的情况

[1,1] 

[1,1,2,2]

tail 不为空

[1,1,2]

[1,2,2]

其他比较正常一点的情况不列出了

 

 

发现思考循环不变式非常有助于清晰思路！！！！

类似的思路有MergeTwoSortedList，partitionList 

回头补充代码 嗯