Java實(shí)現(xiàn)數(shù)組去重復(fù)的18種寫(xiě)法
// 1. 遍歷全部成員盗扒，將當(dāng)前項(xiàng)目與左邊項(xiàng)逐個(gè)進(jìn)行對(duì)比呛凶，如果值相同且下標(biāo)相同表示唯一葱弟，
// 其他則認(rèn)為是重復(fù)項(xiàng)進(jìn)行忽略
static int[] unique1(int arr[]) {
int newArr[] = new int[arr.length];
int x = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j <= i; j++) {
if (arr[i] == arr[j]) {
if (i == j) {
newArr[x] = arr[i];
x++;
}
break;
}
}
}
int result[] = Arrays.copyOf(newArr, x);
return result;
}
// 2. 先將數(shù)組轉(zhuǎn)換為L(zhǎng)ist捣染，利用List的indexOf方法查找下標(biāo)继控，
// 當(dāng)下標(biāo)匹配時(shí)表示唯一侦高，添加到新列表中
static Integer[] unique2(Integer arr[]) {
int x = 0;
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
int l = list.size();
for (int i = 0; i < l; i++) {
if (list.indexOf(arr[i]) == i) {
list.add(arr[i]);
x++;
}
}
// 返回取出的非重復(fù)項(xiàng)
Integer[] result = new Integer[x];
return list.subList(list.size() - x, list.size()).toArray(result);
}
// 3. 在原有列表上移除重復(fù)項(xiàng)目嫉柴。自后往前遍歷，逐個(gè)與前面項(xiàng)比較奉呛，
// 如果值相同且下標(biāo)相同计螺，則移除當(dāng)前項(xiàng)夯尽。
static Integer[] unique3(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
int l = list.size();
while (l-- > 0) {
int i = l;
while (i-- > 0) {
if (list.get(l).equals(list.get(i))) {
list.remove(l);
break;
}
}
}
return list.toArray(new Integer[list.size()]);
}
// 4. 在原有列表上移除重復(fù)項(xiàng)目。自前往后遍歷登馒，逐個(gè)與前面項(xiàng)比較匙握，
// 如果值相同且下標(biāo)相同，則移除前面項(xiàng)陈轿。
static Integer[] unique4(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
int l = list.size();
for (int i = 1; i < l; i++) {
for (int j = 0; j < i; j++) {
if (list.get(i).equals(list.get(j))) {
list.remove(i);
i--;
l--;
break;
}
}
}
return list.toArray(new Integer[list.size()]);
}
// 5. 在原有列表上移除重復(fù)項(xiàng)目圈纺。自前往后遍歷，逐個(gè)與后面項(xiàng)比較麦射，
// 如果值相同且下標(biāo)相同蛾娶，則移除當(dāng)前項(xiàng)。
static Integer[] unique5(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
int l = list.size();
for (int i = 0; i < l; i++) {
for (int j = i + 1; j < l; j++) {
if (list.get(i).equals(list.get(j))) {
list.remove(j);
i--;
l--;
break;
}
}
}
return list.toArray(new Integer[list.size()]);
}
// 6. 利用hashMap屬性唯一性來(lái)實(shí)現(xiàn)去重復(fù)潜秋。
static Integer[] unique6(Integer arr[]) {
Map<Object, Integer> map = new HashMap<Object, Integer>();
for (Integer item : arr) {
if (map.containsKey(item)) {
continue;
}
map.put(item, item);
}
List<Integer> list = new ArrayList<>(map.values());
return list.toArray(new Integer[list.size()]);
}
// 7. 利用filter表達(dá)式蛔琅，即把不符合條件的過(guò)濾掉。需要借助外部列表存儲(chǔ)不重復(fù)項(xiàng)峻呛。
static List<Integer> unique7newArr = new ArrayList<>();
static boolean unique7contains(Integer item) {
if (unique7newArr.indexOf(item) < 0) {
unique7newArr.add(item);
return true;
}
return false;
}
static Integer[] unique7(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
return list.stream().filter(UniqueArray::unique7contains).collect(Collectors.toList())
.toArray(new Integer[UniqueArray.unique7newArr.size()]);
}
// 8. 利用hashSet數(shù)據(jù)結(jié)構(gòu)直接去重復(fù)項(xiàng)罗售。無(wú)序非同步。
static Integer[] unique8(Integer arr[]) {
System.out.print("covert to steam first then to set: ");
Arrays.asList(arr).stream().collect(Collectors.toSet()).forEach(System.out::print);
System.out.println("\ndirectly convert to set:");
Set<Integer> set = new HashSet<>(Arrays.asList(arr));
return new ArrayList<>(set).toArray(new Integer[set.size()]);
}
// 9. 利用LinkedHashSet數(shù)據(jù)結(jié)構(gòu)直接去重復(fù)項(xiàng)钩述。有序鏈表寨躁。
static Integer[] unique9(Integer arr[]) {
Set<Integer> linkedHashSet = new LinkedHashSet<>(Arrays.asList(arr));
return new ArrayList<>(linkedHashSet).toArray(new Integer[linkedHashSet.size()]);
}
// 10. 利用TreeSet數(shù)據(jù)結(jié)構(gòu)直接去重復(fù)項(xiàng)。自然排序和定制排序切距。
static Integer[] unique10(Integer arr[]) {
Set<Integer> treeSet = new TreeSet<>(Arrays.asList(arr)).descendingSet();
return new ArrayList<>(treeSet).toArray(new Integer[treeSet.size()]);
}
// 11. 提前排序朽缎，從后向前遍歷，將當(dāng)前項(xiàng)與前一項(xiàng)對(duì)比谜悟，如果重復(fù)則移除當(dāng)前項(xiàng)
static Integer[] unique11(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
Collections.sort(list);
for (int l = list.size() - 1; l > 0; l--) {
if (list.get(l).equals(list.get(l - 1))) {
list.remove(l);
}
}
return new ArrayList<>(list).toArray(new Integer[list.size()]);
}
// 12. 提前排序话肖，自前往后遍歷，將當(dāng)前項(xiàng)與后一項(xiàng)對(duì)比葡幸，如果重復(fù)則移除當(dāng)前項(xiàng)
static Integer[] unique12(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
Collections.sort(list, Collections.reverseOrder());
int l = list.size() - 1;
for (int i = 0; i < l; i++) {
if (list.get(i).equals(list.get(i + 1))) {
list.remove(i);
i--;
l--;
}
}
return new ArrayList<>(list).toArray(new Integer[list.size()]);
}
// 13. 轉(zhuǎn)為stream最筒，利用distinct方法去重復(fù)
static Integer[] unique13(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
list = list.stream().distinct().collect(Collectors.toList());
return new ArrayList<>(list).toArray(new Integer[list.size()]);
}
// 14. 雙循環(huán)自右往左逐個(gè)與左側(cè)項(xiàng)對(duì)比，如遇相同則跳過(guò)當(dāng)前項(xiàng)
// 下一項(xiàng)為當(dāng)前項(xiàng)蔚叨，繼續(xù)逐個(gè)與左側(cè)項(xiàng)對(duì)比
static Integer[] unique14(Integer arr[]) {
int len = arr.length;
Integer[] result = new Integer[len];
int x = len;
for (int i = len - 1; i >= 0; i--) {
for (int j = i - 1; j >= 0; j--) {
if (arr[i].equals(arr[j])) {
i--;
j = i;
}
}
// 非重復(fù)項(xiàng)的為唯一床蜘，追加到新數(shù)組
result[--x] = arr[i];
}
return Arrays.copyOfRange(result, x, len);
}
// 15. 利用Interator來(lái)遍歷List，如果不在新列表中則添加
static Integer[] unique15(Integer arr[]) {
List<Integer> list = new ArrayList<>(Arrays.asList(arr));
List<Integer> result = new ArrayList<>();
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
Integer item = it.next();
if (!result.contains(item)) {
result.add(item);
}
}
return new ArrayList<>(result).toArray(new Integer[result.size()]);
}
// 16. 利用遞歸調(diào)用來(lái)去重復(fù)蔑水。遞歸自后往前逐個(gè)調(diào)用邢锯，當(dāng)長(zhǎng)度為1時(shí)終止。
// 當(dāng)后一項(xiàng)與前任一項(xiàng)相同說(shuō)明有重復(fù)搀别，則刪除當(dāng)前項(xiàng)丹擎。相當(dāng)于利用自我調(diào)用來(lái)替換循環(huán)
static Integer[] uniqueRecursion1(Integer arr[],
int len, List<Integer> result) {
int last = len - 1;
Integer lastItem = arr[last];
int l = last;
boolean isRepeat = false;
if (len <= 1) {
result.add(0, lastItem);
return new ArrayList<>(result).toArray(new Integer[result.size()]);
}
while (l-- > 0) {
if (lastItem.equals(arr[l])) {
isRepeat = true;
break;
}
}
// 如果不重復(fù)表示唯一，則添加到新數(shù)組中
if (!isRepeat) {
result.add(0, lastItem);
}
return uniqueRecursion1(arr, len - 1, result);
}
// 17. 利用遞歸調(diào)用來(lái)去重復(fù)的另外一種方式。遞歸自后往前逐個(gè)調(diào)用蒂培，當(dāng)長(zhǎng)度為1時(shí)終止再愈。
// 與上一個(gè)遞歸不同，這里將不重復(fù)的項(xiàng)目作為結(jié)果拼接起來(lái)
static List<Integer> uniqueRecursion2(List<Integer> arr, int len) {
if (len <= 1) {
System.out.println("last arr:" + arr);
return arr;
}
int last = len - 1;
int l = last - 1;
boolean isRepeat = false;
Integer lastItem = arr.get(last);
while (l >= 0) {
if (lastItem.equals(arr.get(l))) {
isRepeat = true;
break;
}
l--;
}
// 如果不重復(fù)則添加到臨時(shí)列表护戳，最后將全部結(jié)果拼接
List<Integer> result = new ArrayList<>();
arr.remove(last);
if (!isRepeat) {
result.add(lastItem);
}
return Stream.concat(uniqueRecursion2(arr, len - 1).stream(),
result.stream()).collect(Collectors.toList());
}
// 18. 雙重循環(huán)翎冲，將左側(cè)項(xiàng)逐個(gè)與當(dāng)前項(xiàng)比較。
// 如果遇到值相等則跳出循環(huán)比較下標(biāo)媳荒，
// 若下標(biāo)相同表示第一次出現(xiàn)則追加到新數(shù)組抗悍。
// 這里與第1個(gè)方案稍微不同。
static Integer[] unique18(Integer arr[]) {
Integer newArr[] = new Integer[arr.length];
int x = 0;
for (int i = 0; i < arr.length; i++) {
int j = 0;;
for (; j < i; j++) {
if (arr[i].equals(arr[j])) {
break;
}
}
if (i == j) {
newArr[x] = arr[i];
x++;
}
}
return Arrays.copyOf(newArr, x);
}
// 測(cè)試用例
public static void main(final String args[]) {
int arr1[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
int[] result;
long startTime;
// 1.
System.out.println("unique1 start:" + Arrays.toString(arr1));
startTime = System.currentTimeMillis();
result = UniqueArray.unique1(arr1);
System.out.println("unique1 result:" + Arrays.toString(result));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 2.
Integer arr2[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique2 start:" + Arrays.toString(arr2));
startTime = System.currentTimeMillis();
Integer result2[] = UniqueArray.unique2(arr2);
System.out.println("unique2 result:" + Arrays.toString(result2));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 3.
Integer arr3[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique3 start:" + Arrays.toString(arr2));
startTime = System.currentTimeMillis();
Integer result3[] = UniqueArray.unique3(arr3);
System.out.println("unique3 result:" + Arrays.toString(result3));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 4.
Integer arr4[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique4 start:" + Arrays.toString(arr4));
startTime = System.currentTimeMillis();
Integer result4[] = UniqueArray.unique4(arr4);
System.out.println("unique4 result:" + Arrays.toString(result4));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 5.
Integer arr5[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique5 start:" + Arrays.toString(arr5));
startTime = System.currentTimeMillis();
Integer result5[] = UniqueArray.unique5(arr5);
System.out.println("unique5 result:" + Arrays.toString(result5));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 6.
Integer arr6[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique6 start:" + Arrays.toString(arr6));
startTime = System.currentTimeMillis();
Integer result6[] = UniqueArray.unique6(arr6);
System.out.println("unique6 result:" + Arrays.toString(result6));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 7.
Integer arr7[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique7 start:" + Arrays.toString(arr7));
startTime = System.currentTimeMillis();
Integer result7[] = UniqueArray.unique7(arr7);
System.out.println("unique7 result:" + Arrays.toString(result7));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 8.
Integer arr8[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique8 start:" + Arrays.toString(arr8));
startTime = System.currentTimeMillis();
Integer result8[] = UniqueArray.unique8(arr8);
System.out.println("unique8 result:" + Arrays.toString(result8));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 9.
Integer arr9[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique9 start:" + Arrays.toString(arr9));
startTime = System.currentTimeMillis();
Integer result9[] = UniqueArray.unique9(arr9);
System.out.println("unique9 result:" + Arrays.toString(result9));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 10.
Integer arr10[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique10 start:" + Arrays.toString(arr10));
startTime = System.currentTimeMillis();
Integer result10[] = UniqueArray.unique10(arr10);
System.out.println("unique10 result:" + Arrays.toString(result10));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 11.
Integer arr11[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique11 start:" + Arrays.toString(arr11));
startTime = System.currentTimeMillis();
Integer result11[] = UniqueArray.unique11(arr11);
System.out.println("unique11 result:" + Arrays.toString(result11));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 12.
Integer arr12[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique12 start:" + Arrays.toString(arr12));
startTime = System.currentTimeMillis();
Integer result12[] = UniqueArray.unique12(arr12);
System.out.println("unique12 result:" + Arrays.toString(result12));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 13.
Integer arr13[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique13 start:" + Arrays.toString(arr13));
startTime = System.currentTimeMillis();
Integer result13[] = UniqueArray.unique13(arr13);
System.out.println("unique13 result:" + Arrays.toString(result13));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 14.
Integer arr14[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique14 start:" + Arrays.toString(arr14));
startTime = System.currentTimeMillis();
Integer result14[] = UniqueArray.unique14(arr14);
System.out.println("unique14 result:" + Arrays.toString(result14));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 15.
Integer arr15[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique15 start:" + Arrays.toString(arr15));
startTime = System.currentTimeMillis();
Integer result15[] = UniqueArray.unique15(arr15);
System.out.println("unique15 result:" + Arrays.toString(result15));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 16.
Integer arr16[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("uniqueRecursion1 start:" + Arrays.toString(arr16));
startTime = System.currentTimeMillis();
Integer result16[] = UniqueArray.uniqueRecursion1(arr16, arr16.length, new ArrayList<>());
System.out.println("uniqueRecursion1 result:" + Arrays.toString(result16));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 17.
Integer arr17[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("uniqueRecursion2 start:" + Arrays.toString(arr17));
startTime = System.currentTimeMillis();
List<Integer> result17 = UniqueArray.uniqueRecursion2(new ArrayList<>(Arrays.asList(arr17)), arr17.length);
System.out.println("uniqueRecursion2 result:" + result17);
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
// 18.
Integer arr18[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
System.out.println("unique18 start:" + Arrays.toString(arr18));
startTime = System.currentTimeMillis();
Integer result18[] = UniqueArray.unique18(arr18);
System.out.println("unique18 result:" + Arrays.toString(result18));
System.out.println("\r\ntime:" + (System.currentTimeMillis() - startTime) + " ms.");
}
