Java實(shí)現(xiàn)刪除排序數(shù)組中重復(fù)元素的方法小結(jié)【三種方法比較】

更新時間：2019年02月23日 11:53:24 作者：PayneWoo

這篇文章主要介紹了Java實(shí)現(xiàn)刪除排序數(shù)組中重復(fù)元素的方法,結(jié)合實(shí)例形式對比分析了三種常見的數(shù)組元素刪除算法操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Java實(shí)現(xiàn)刪除排序數(shù)組中重復(fù)元素的方法。分享給大家供大家參考，具體如下：

題目描述：

給定一個排序數(shù)組，在原數(shù)組中刪除重復(fù)出現(xiàn)的數(shù)字，使得每個元素只出現(xiàn)一次，并且返回新的數(shù)組的長度。

不要使用額外的數(shù)組空間，必須在原地沒有額外空間的條件下完成。

一：通過ArrayList解決

時間復(fù)雜度和空間復(fù)雜度都為O(n)

ArrayList<Integer> list = new ArrayList<Integer>();
// 去掉數(shù)組中重復(fù)的元素
public int removeTheagain01(int[] array) {
    if (array == null || array.length == 0) {
      return 0;
    } else if (array.length == 1) {
      return 1;
    } else {
      int i = 0;
      int n = array.length - 1;
      while (i <= n) {
        if (i == n) {
          list.add(array[i]);
          i++;
        } else {
          int j = i + 1;
          if (array[i] == array[j]) {
            while (j <= n && array[i] == array[j]) {
              j++;
            }
          }
          list.add(array[i]);
          i = j;
        }
      }
      for (int k = 0; k < list.size(); k++) {
        array[k] = list.get(k);
      }
      return list.size();
    }
}

二：利用System.arraycopy（）函數(shù)來復(fù)制數(shù)組

時間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)

public int removeTheagain02(int[] array) {
    if (array == null || array.length == 0) {
      return 0;
    } else if (array.length == 1) {
      return 1;
    } else {
      int end = array.length - 1;
      for (int i = 0; i <= end; i++) {
        if (i < end) {
          int j = i + 1;
          if (array[i] == array[j]) {
            while (j <= end && array[i] == array[j]) {
              j++;
            }
          }
          System.arraycopy(array, j, array, i + 1, end - j + 1);
          end -= j - i - 1;
        }
      }
      return end + 1;
    }
}

三：借助臨時變量解決問題

時間復(fù)雜度O(N),空間復(fù)雜度O(1)

public int removeTheagain03(int[] array) {
    if (array == null || array.length == 0) {
      return 0;
    } else if (array.length == 1) {
      return 1;
    } else {
      int temp = array[0];
      int len = 1;
      for (int i = 1; i < array.length; i++) {
        if (temp == array[i]) {
          continue;
        } else {
          temp = array[i];
          array[len] = array[i];
          len++;
        }
      }
      return len;
    }
}

總結(jié)：

數(shù)組下標(biāo)（指針）與臨時變量，是解決數(shù)組相關(guān)面試題的兩大法寶**

PS：本站還有兩款比較簡單實(shí)用的在線文本去重復(fù)工具，推薦給大家使用：

在線去除重復(fù)項(xiàng)工具：
http://tools.jb51.net/code/quchong

在線文本去重復(fù)工具：
http://tools.jb51.net/aideddesign/txt_quchong

更多關(guān)于java相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)組操作技巧總結(jié)》、《Java字符與字符串操作技巧總結(jié)》、《Java數(shù)學(xué)運(yùn)算技巧總結(jié)》、《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》及《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》

希望本文所述對大家java程序設(shè)計有所幫助。

您可能感興趣的文章: