删除已排序數組中的重複元素

題目1

題目：删除數組中重複的元素，數組是排好序的，使所有的元素都隻出現一次，如{1,1,2,3}變為{1,2,3}，不允許申請額外的數組。

時間複雜度：O（n）

空間複雜度：O（1）

思路比較難表達清楚，其實隻要畫個圖就很好了解，前後兩個索引 index 與 i，隻要出現重複元素index就呆在原地不動，i繼續往前走，index與i之間的元素都是重複的元素。

package com.cn;

public class DeleteRepeatElement {
    public static void main(String[] args) {

        int[] a = new int[]{,,,,,,};

        Delete(a);
    }

    public static void Delete(int[] a){
        int n = a.length - ;
        int index = ;
        for(int i = ; i <= n; i++){
            if(a[i] != a[index]){
                index++;
                a[index] = a[i];
            }
        }

        for(int j = ; j <= index; j++){
            System.out.print(a[j] + " ");
        }
    }

}
           

題目2

題目：同上題，數組中的元素最多出現兩次

重複的元素最多出現兩次，而且數組是排好序的，是以可以不管前兩個元素，第三個元素與第一個元素比較，如果第三個元素與第一個元素是相同的，則說明這三個元素都是相同的，第三個元素的位置需要被别的元素替換掉，是以index呆在原地不動，等待不與他相同的元素，同理index與i之間的元素都是重複的元素。

package com.cn;

public class TwoRepeatElement {
    public static void main(String[] args) {
        int[] a = new int[]{,,,,,};
        Delete(a);
    }

    public static void Delete(int[] a){
        int n = a.length - ;
        int index = ;
        for(int i = ; i <= n; i++){
            if(a[i] != a[index - ]){
                a[index] = a[i];
                index++;
            }
        }

        for(int j = ; j < index; j++ ){
            System.out.print(a[j] + " ");
        }
    }

}