Java数组与列表去重的18种方法

Java
307
0
0
2023-10-20
2022最新java基础，语法面试题168题及答案（已拿Offer）
上一篇
java笔试题50道 收藏版
下一篇
标签   JavaScript基础

说明

在实际编程中，经常会遇到数组或列表去掉重复项，以保持成员唯一性。各个语言的实现方式均不尽相同。针对数组去重，Java实现方式有多种，比如新建数组来存储非重复项，或者在原有基础上删除掉重复的项，也可以利用数据结构Set或ArrayList来达到去重复。以下18种方式都可以实现，但每一种方法都不尽相同，有的很简单，几行代码搞定，有的则稍复杂，需要10来行代码。通过对比不同的实现，我们可以从中发现Java语言里一些不同的东西。

方式

 //1. 双循环遍历全部成员，将当前项目与左边项逐个进行对比，如果值相同且下标相同表示唯一，其他则认为是重复项进行忽略。
static int[] unique(int arr[]) {
  int newArr[] = new int[arr.length];
  int x =;
  for (int i =, l = arr.length; i < l; i++) {
    for (int j =; 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. 先将数组转换为List，利用List的indexOf方法查找下标，当下标匹配时表示唯一，添加到新列表中
static  Integer [] unique2(Integer arr[]) {
  int x =;
  List<Integer> list = new ArrayList<>(Arrays.asList(arr));
  int l = list.size();
  for (int i =; i < l; i++) {
    if (list.indexOf(arr[i]) == i) {
      list.add(arr[i]);
      x++;
    }
  }
  // 返回取出的非重复项
  Integer[] result = new Integer[x];
  return list.subList(list.size() - x, list.size()).toArray(result);
} 
 
 //3. 在原有列表上移除重复项目。自后往前遍历，逐个与前面项比较，如果值相同且下标相同，则移除当前项。
static Integer[] unique(Integer arr[]) {
  List<Integer> list = new ArrayList<>(Arrays.asList(arr));
  int l = list.size();
  while (l-- >) {
    int i = l;
    while (i-- >) {
      if (list.get(l).equals(list.get(i))) {
        list.remove(l);
        break;
      }
    }
  }
  return list.toArray(new Integer[list.size()]);
} 
 
 //4. 在原有列表上移除重复项目。自前往后遍历，逐个与前面项比较，如果值相同且下标相同，则移除前面项。
static Integer[] unique(Integer arr[]) {
  List<Integer> list = new ArrayList<>(Arrays.asList(arr));
  int l = list.size();
 
  for (int i =; i < l; i++) {
    for (int j =; 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. 在原有列表上移除重复项目。自前往后遍历，逐个与后面项比较，如果值相同且下标相同，则移除当前项。
static Integer[] unique(Integer arr[]) {
  List<Integer> list = new ArrayList<>(Arrays.asList(arr));
  int l = list.size();
  for (int i =; i < l; i++) {
    for (int j = i +; 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属性唯一性来实现去重复。
static Integer[] unique(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表达式，即把不符合条件的过滤掉。需要借助外部列表存储不重复项。
static List<Integer> uniquenewArr = new ArrayList<>();
 
static boolean uniquecontains(Integer item) {
  if (uniquenewArr.indexOf(item) < 0) {
    uniquenewArr.add(item);
    return true;
  }
  return false;
}
 
static Integer[] unique(Integer arr[]) {
  List<Integer> list = new ArrayList<>(Arrays.asList(arr));
  return list.stream().filter(UniqueArray::uniquecontains).collect(Collectors.toList())
    .toArray(new Integer[UniqueArray.uniquenewArr.size()]);
} 
 
 //8. 利用hashSet数据结构直接去重复项。无序非同步。
static Integer[] unique(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数据结构直接去重复项。有序链表。
static Integer[] unique(Integer arr[]) {
  Set<Integer> linkedHashSet = new LinkedHashSet<>(Arrays.asList(arr));
  return new ArrayList<>(linkedHashSet).toArray(new Integer[linkedHashSet.size()]);
} 
 
 //10. 利用TreeSet数据结构直接去重复项。自然排序和定制排序。
static Integer[] unique(Integer arr[]) {
  Set<Integer> treeSet = new TreeSet<>(Arrays.asList(arr)).descendingSet();
  return new ArrayList<>(treeSet).toArray(new Integer[treeSet.size()]);
} 
 
 //11. 提前排序，从后向前遍历，将当前项与前一项对比，如果重复则移除当前项
static Integer[] unique(Integer arr[]) {
  List<Integer> list = new ArrayList<>(Arrays.asList(arr));
  Collections.sort(list);
  for (int l = list.size() -; l > 0; l--) {
    if (list.get(l).equals(list.get(l -))) {
      list.remove(l);
    }
  }
  return new ArrayList<>(list).toArray(new Integer[list.size()]);
} 
 
 //12. 提前排序，自前往后遍历，将当前项与后一项对比，如果重复则移除当前项
static Integer[] unique(Integer arr[]) {
  List<Integer> list = new ArrayList<>(Arrays.asList(arr));
  Collections.sort(list, Collections.reverseOrder());
  int l = list.size() -;
  for (int i =; i < l; i++) {
    if (list.get(i).equals(list.get(i +))) {
      list.remove(i);
      i--;
      l--;
    }
  }
  return new ArrayList<>(list).toArray(new Integer[list.size()]);
} 
 
 //13. 转为stream，利用distinct方法去重复
static Integer[] unique(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. 双循环自右往左逐个与左侧项对比，如遇相同则跳过当前项，下一项为当前项，继续逐个与左侧项对比
static Integer[] unique(Integer arr[]) {
  int  len  = arr.length;
  Integer[] result = new Integer[len];
  int x = len;
  for (int i = len -; i >= 0; i--) {
    for (int j = i -; j >= 0; j--) {
      if (arr[i].equals(arr[j])) {
        i--;
        j = i;
      }
    }
    // 非重复项的为唯一，追加到新数组
    result[--x] = arr[i];
  }
  return Arrays.copyOfRange(result, x, len);
} 
 
 //15. 利用Interator来遍历List，如果不在新列表中则添加
static Integer[] unique(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. 利用递归调用来去重复。递归自后往前逐个调用，当长度为1时终止。
// 当后一项与前任一项相同说明有重复，则删除当前项。相当于利用自我调用来替换循环
static Integer[] uniqueRecursion(Integer arr[], int len, List<Integer> result) {
  int last = len -;
  Integer lastItem = arr[last];
  int l = last;
  boolean isRepeat = false;
  if (len <=) {
    result.add(, lastItem);
    return new ArrayList<>(result).toArray(new Integer[result.size()]);
  }
  while (l-- >) {
    if (lastItem.equals(arr[l])) {
      isRepeat = true;
      break;
    }
  }
  // 如果不重复表示唯一，则添加到新数组中
  if (!isRepeat) {
    result.add(, lastItem);
  }
  return uniqueRecursion(arr, len - 1, result);
} 
 
 //17. 利用递归调用来去重复的另外一种方式。递归自后往前逐个调用，当长度为1时终止。
// 与上一个递归不同，这里将不重复的项目作为结果拼接起来
static List<Integer> uniqueRecursion(List<Integer> arr, int len) {
  if (len <=) {
    System.out.println("last arr:" + arr);
    return arr;
  }
 
  int last = len -;
  int l = last -;
  boolean isRepeat = false;
  Integer lastItem = arr.get(last);
  while (l >=) {
    if (lastItem.equals(arr.get(l))) {
      isRepeat = true;
      break;
    }
    l--;
  }
 
  // 如果不重复则添加到临时列表，最后将全部结果拼接
  List<Integer> result = new ArrayList<>();
  arr.remove(last);
  if (!isRepeat) {
    result.add(lastItem);
  }
  return Stream.concat(uniqueRecursion(arr, len - 1).stream(), result.stream()).collect(Collectors.toList());
} 
 
 //18. 双重循环，将左侧项逐个与当前项比较。如果遇到值想等则比较下标，下标相同则追加到新数组。这里与第1个方案稍微的不同。
static Integer[] unique(Integer arr[]) {
  Integer newArr[] = new Integer[arr.length];
  int x =;
  for (int i =; i < arr.length; i++) {
    int j =;;
    for (; j < i; j++) {
      if (arr[i].equals(arr[j])) {
        break;
      }
    }
    if (i == j) {
      newArr[x] = arr[i];
      x++;
    }
  }
  return Arrays.copyOf(newArr, x);
}

执行测试

 import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
public class UniqueArray {
  
 // 此处省略代码...
 
    public static void main(final String args[]) {
    int arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    int[] result;
    long startTime;
      int arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    int[] result;
    long startTime;
    //.
    System.out.println("unique start:" + Arrays.toString(arr1));
    startTime = System.currentTimeMillis();
    result = UniqueArray.unique(arr1);
    System.out.println("unique result:" + Arrays.toString(result));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + "  ms .");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr2));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique2(arr2);
    System.out.println("unique result:" + Arrays.toString(result2));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr2));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique3(arr3);
    System.out.println("unique result:" + Arrays.toString(result3));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr4));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique4(arr4);
    System.out.println("unique result:" + Arrays.toString(result4));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr5));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique5(arr5);
    System.out.println("unique result:" + Arrays.toString(result5));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr6));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique6(arr6);
    System.out.println("unique result:" + Arrays.toString(result6));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr7));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique7(arr7);
    System.out.println("unique result:" + Arrays.toString(result7));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr8));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique8(arr8);
    System.out.println("unique result:" + Arrays.toString(result8));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr9));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique9(arr9);
    System.out.println("unique result:" + Arrays.toString(result9));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr10));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique10(arr10);
    System.out.println("unique result:" + Arrays.toString(result10));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr11));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique11(arr11);
    System.out.println("unique result:" + Arrays.toString(result11));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr12));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique12(arr12);
    System.out.println("unique result:" + Arrays.toString(result12));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr13));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique13(arr13);
    System.out.println("unique result:" + Arrays.toString(result13));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr14));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique14(arr14);
    System.out.println("unique result:" + Arrays.toString(result14));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr15));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique15(arr15);
    System.out.println("unique result:" + Arrays.toString(result15));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("uniqueRecursion start:" + Arrays.toString(arr16));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.uniqueRecursion1(arr16, arr16.length, new ArrayList<>());
    System.out.println("uniqueRecursion result:" + Arrays.toString(result16));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("uniqueRecursion start:" + Arrays.toString(arr17));
    startTime = System.currentTimeMillis();
    List<Integer> result = UniqueArray.uniqueRecursion2(new ArrayList<>(Arrays.asList(arr17)), arr17.length);
    System.out.println("uniqueRecursion result:" + result17);
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");
 
    //.
    Integer arr[] = { 1, 3, -1, 1, 2, 2, 4, 2, 2, -1 };
    System.out.println("unique start:" + Arrays.toString(arr18));
    startTime = System.currentTimeMillis();
    Integer result[] = UniqueArray.unique18(arr18);
    System.out.println("unique result:" + Arrays.toString(result18));
    System.out.println("rntime:" + (System.currentTimeMillis() - startTime) + " ms.");

打印结果

 
 MacBook-Pro:unique jarry$ java --version java.0.1 2018-04-17
 Java(TM) SE Runtime Environment.3 (build 10.0.1+10) Java HotSpot(TM)
-Bit Server VM 18.3 (build 10.0.1+10, mixed mode)
 
MacBook-Pro:unique jarry$ javac UniqueArray.java 
MacBook-Pro:unique jarry$ java UniqueArray
unique start:[1, 3, -1, 1, 2, 2, 4, 2, 2, -1]
unique result:[1, 3, -1, 2, 4]
 
time: ms.
unique start:[1, 3, -1, 1, 2, 2, 4, 2, 2, -1]
unique result:[1, 3, -1, 2, 4]
 
// ...其他省略...etc
 
time: ms.
uniqueRecursion start:[1, 3, -1, 1, 2, 2, 4, 2, 2, -1]
last arr:[]
uniqueRecursion result:[1, 3, -1, 2, 4]
 
time: ms.
unique start:[1, 3, -1, 1, 2, 2, 4, 2, 2, -1]
unique result:[1, 3, -1, 2, 4]

思考

通过去重复的多种实现，其实是让我们更了解Java语言，还可以让我们根据场景采用不用方式，毕竟业务场景千差万别。你常用哪几种方式？你还有其他的实现方式吗？

2022最新java基础，语法面试题168题及答案（已拿Offer）
上一篇
java笔试题50道 收藏版
下一篇