时间戳

首页 > 解决方案 > 有没有办法在不重复整数的情况下将 int[] 复制到另一个 int[] ？

java - 有没有办法在不重复整数的情况下将 int[] 复制到另一个 int[] ？

问题描述

我们不能使用ArrayList或类似的东西，因为老师告诉我们不要使用它们，所以我就卡在了这一点上。该函数的签名是：

public static int[] deleteNth(int[] elements, int maxOccurrences){}

我已经遍历数组并获得了int result[]我将返回的副本的长度，但现在我陷入了思考如何粘贴某些元素的问题。我写了方法的I/O：

deleteNth(new int[] {20,37,20,21}, 1) // return [20,37,21]
deleteNth(new int[] {1,1,3,3,7,2,2,2,2}, 3) // return [1, 1, 3, 3, 7, 2, 2, 2]

在我的最后一次机会中，我尝试了这样的事情，但我的大脑筋疲力尽

for(int n:result) {
 int n1=0;
 boolean nope=false;
 for(;n1<elements.length;) {
  //TODOthings
 }
 result[n]=elements[n1];
}

对于那些不相信我的人，这是我的代码：

public static int[] deleteNth(int[] elements, int maxOccurrences) {
        int[] result = null;
        if (elements != null && maxOccurrences > 0) {
            int result_lenght=elements.length;
            int ocurrences=0;
            for(int n:elements) {
                for(int n1:elements) {
                    if(n==n1 && ocurrences!=maxOccurrences) {
                        ocurrences++;
                        result_lenght--;
                    }
                }
            }
            result=new int[result_lenght];
            for(int n:result) {
                int n1=0;
                boolean nope=false;
                for(;n1<elements.length;) {
                    //todothings
                }
                result[n]=elements[n1];
            }
        }else {
            result=elements;
        }
        return result;
    }

标签： javaarrays

解决方案

由于在此任务中不允许使用诸如SetorMap和适当的实现之类的库设施，并且重新发明重新实现这些类的轮子似乎比必要的复杂得多，因此可以基于使用对象包装器来实现一个简单的解决Integer方案int用于null标记应删除的值。

所以算法如下：

  1. 将输入转换int[]为Integer[]
  2. 初始化nullCount，使用嵌套循环，找到超过阈值的重复值并将它们设置为null随着增加nullCount
  3. 创建结果数组，复制非空值并返回。

示例实现：

public static int[] deleteNth(int[] elements, int maxOccurrences) {
    Integer[] arr = new Integer[elements.length];
    int i = 0;
    for (Integer x : elements) {
        arr[i++] = x;
    }
    
    int nullCount = 0;
    for (i = 0; i < arr.length; i++) {
        Integer x = arr[i];
        if (null == x) {
            continue;
        }
        int cnt = 1;
        for (int j = i + 1; j < arr.length; j++) {
            Integer y = arr[j];
            if (null == y) {
                continue;
            }
            if (x.equals(y)) {
                cnt++;
                if (cnt > maxOccurrences) {
                    arr[j] = null;
                    nullCount++;
                }
            }
        }
    }
    int[] result = new int[arr.length - nullCount];
    i = 0;
    for (int j = 0; j < arr.length; j++) {
        Integer x = arr[j];
        if (null != x) {
            result[i++] = x;
        }
    }
    return result;
}

测试和输出：

System.out.println(Arrays.toString(deleteNth(new int[] {20,37,20,21}, 1))); // return [20,37,21]
System.out.println(Arrays.toString(deleteNth(new int[] {1,1,3,3,7,2,2,2,2}, 3))); // return [1, 1, 3, 3, 7, 2, 2, 2]

输出：

[20, 37, 21]
[1, 1, 3, 3, 7, 2, 2, 2]

更快的版本可以使用额外的布尔数组来跟踪重复值，以便可以在嵌套循环中跳过它们。

基于流的解决方案（仅供参考和比较）如下所示：

  • 使用数组元素作为键和值准备初始映射 - 使用索引列表Collectors.groupingBy
  • 重新映射初始映射中的条目：索引 -> 键（数组元素）使用flatMap并Stream::limit遵守阈值
  • 按索引对新条目进行排序
  • 检索值并将它们收集到数组
public static int[] deleteNth(int[] arr, int threshold) {
    return IntStream
            .range(0, arr.length)
            .boxed()
            .collect(Collectors.groupingBy(
                i -> arr[i], 
                Collectors.mapping(i -> i, Collectors.toList())
            ))
            .entrySet()
            .stream()
            .flatMap(e -> e.getValue().stream()
                    .limit(threshold)
                    .map(ix -> Map.entry(ix, e.getKey())) // Map.entry since Java 9
            )
            .sorted(Map.Entry.comparingByKey())
            .mapToInt(Map.Entry::getValue)
            .toArray();
}

推荐阅读