如何去除有序数组中的重复元素

题目要求：输入一个有序的数组，你需要原地删除重复的元素，使得每个元素只能出现一次，返回去重后新数组的长度

题目分析：原地删除，即不可以创建新的辅助数组，那么需要在原数组上修改解决。

这种一般采用双指针技巧

即：如果是普通数组，使用两个指针slow和fast，fast负责网后遍历，如果发现数组元素不同，则把slow下标值对应的值替换为fast下标值对应的值，则在原数组上完成保存不重复值的操作，如果元素重复，则fast前进，而slow不动，则最终fast遍历到末尾时，slow下标值对应的所有元素已经是不重复的有序数组元素了

/**
 * 有序数组或者链表，通过两个指针方式去重数据，统计去重后数组个数
 */
public class ArraysTest {

    public static void main(String[] args) {
        int [] arrays = new int[7];
        arrays[0] = 0;
        arrays[1] = 1;
        arrays[2] = 1;
        arrays[3] = 2;
        arrays[4] = 3;
        arrays[5] = 3;
        arrays[6] = 4;
        System.out.println(removeDuplicates(arrays));
    }

    public static int removeDuplicates(int[] nums) {
        int slow = 0;
        int fast = 1;
        int length = nums.length;
        while (fast < length) {
            if(nums[slow] != nums[fast]){
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow+1;
    }
}

　　扩展问题，如果是有序链表呢，方式一样处理，代码如下

/**
 * 有序数组或者链表，通过两个指针方式去重数据，统计去重后数组个数
 */
public class LinkedArraysTest {


    public static void main(String[] args) {

        LinkedList linkedList = new LinkedList();
        linkedList.add(new Node(0));
        linkedList.add(new Node(1));
        linkedList.add(new Node(1));
        linkedList.add(new Node(2));
        linkedList.add(new Node(3));
        linkedList.add(new Node(4));
        linkedList.add(new Node(4));
        Node head = removeDulplicated(linkedList);
        int count = 0;
        while (head !=null){
            count++;
            head = head.next;
        }
        System.out.println(count);
    }

    public static Node removeDulplicated(LinkedList linkedList) {

        Node slow = linkedList.head;
        Node fast = linkedList.head.next;
        while (null != fast){
            if(slow.data != fast.data){
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next;
        }
        slow.next =null;
        return linkedList.head;
    }

    public static class Node{
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }

    }

    public static class LinkedList{
        Node head;

        public void add(Node node){
            if(null == head){
                head = node;
            }else{
                Node current = head;
                while (current.next != null){
                    current = current.next;
                }
                current.next = node;
            }
        }
    }

}