对数组中所有匹配的整数元素求和

我正在研究面试中可能提出的一些基本问题。使用基本的 for 循环(没有哈希映射等)我想总结数组中的所有匹配元素。例如，在下面的示例中，将产生 6 个匹配元素(匹配：6)，总共产生 36 个元素。这方面的一个例子可能是掷骰子，分数是匹配的所有骰子的总和。

public static void main(String[] args) {
int arr[] = {6,6,6,6,6,6};
int matched = 1;
int value = 0;
int total = 0;  
for(int i=0;i<arr.length;i++){
for(int j=(i+1);j<arr.length;j++){
if(ar[i] == ar[j]){
matched++;
value = ar[i];
break;  
}
}
total = (matched * value);
} // End for loop
System.out.println("Matched:"+(matched)+"");
System.out.println("Total:"+total);         
}

但是，如果数组是例如...

int arr[] = {6,1,1,6,6,6};

我得到的输出将是(匹配：5)，总共 30.我可以存储匹配的 1 对并使用尽可能少的基本代码将它们添加到总数中吗？

将问题解释为"提供多次出现的值的总数及其总和">，并考虑到不能使用诸如地图之类的"花哨"(原文如此)：

int[] array = {6, 1, 1, 6, 6, 6};
int sum = 0;
int matches = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
if (i != j && array[i] == array[j]) {
sum += array[i];
matches++;
break;
}
}
}
System.out.println(matches); // 6
System.out.println(sum); // 26

如果你被允许使用数组 - 如果不是太花哨 - 那么你可以使用3个循环：

第一个找到最小和最大元素
第二个确定每个项目的出现
第三个计算总数

在Java中，这看起来像这样：

public static void main(String[] args) {
int[] array = {6, 3, 3, 6, 6, 6, 4, 4, 20};
int min = array[0];
int max = array[0];
// Find min max
for (int i : array) {
if (i < min) {
min = i;
}
if (i > max) {
max = i;
}
}
// Use array to sum up all elements
int[] holderArray = new int[max - min + 1];
for (int i : array) {
holderArray[i - min]++;
}
// Calculate occurrence and sums
for(int i = 0; i < holderArray.length; i++) {
if(holderArray[i] > 0) {
System.out.printf("number: %2d; count: %2d; sum: %2d%n", i + min, holderArray[i], (i + min) * holderArray[i]);
}
}
}

这将打印出来：

number:  3; count:  2; sum:  6
number:  4; count:  2; sum:  8
number:  6; count:  4; sum: 24
number: 20; count:  1; sum: 20

我不完全理解你的问题，但根据我的理解，你想得到所有匹配数字的总和，如果它大于 1？在这种情况下，您可以使用 O(n) 解决方案。

创建一个空Map然后迭代数组，如果当前数字不在映射中，则将其添加到值为1的映射中，如果当前元素已经存在于映射中，则只需递增它的值 (val++)，最后您将有一个映射，对于每个key(每个不同的数字)，您将拥有数组中匹配的数字数量作为价值。您需要做的就是遍历key,val对，将每个key*val相乘，然后将乘以的值相加，即可获得正确的总数。如果你只需要匹配的数量，你可以在另一个变量中只对vals求和。

所以对于数组[1,1,5,1,5,2,2,5,1]，你的地图将是这样的：

{1:4, 2:2, 5:3}，

和您的总计：

total matches: 9

total: 23

我希望这有帮助！

这是我刚刚写的代码片段。此方法接收整数数组，并创建每个唯一整数的映射，并在列表中计数。在该方法的第二部分中，迭代 HashMap 对象countOfNumbersMap并打印每个元素的总和。

private void findSumOfMatchingNumbers(int array[]) {
HashMap<Integer, Integer> countOfNumbersMap = new HashMap<>();
// Setting up the map of unique integers and it's count
for (int i = 0 ; i < array.length ; i++) {
if (countOfNumbersMap.containsKey(array[i])) {
int currentCount = countOfNumbersMap.get(array[i]);
countOfNumbersMap.put(array[i], currentCount + 1);
} else {
countOfNumbersMap.put(array[i], 1);
}
}
for (Integer integer : countOfNumbersMap.keySet()) {
int sum = countOfNumbersMap.get(integer) * integer;
System.out.println(String.format("Number = %d, Sum = %d", integer, sum));
}
}

程序的最坏运行时是 O(n)。

如果整数的范围有限，最简单的方法是创建一个直方图(即创建一个数组，其中在索引i下存储数字的出现次数i)。由此，很容易找到多次出现的元素，并将它们汇总起来。此解决方案的复杂度为 O(n+k)，其中 k 是整数的范围。

另一种解决方案是对数组进行排序，然后匹配的数字将彼此相邻，并且很容易计数。这具有O(nlogn)复杂性。

如果不允许这些方法，下面是 O(n^2) 中仅使用 for 循环的解决方案：

总结整个数组
使用双循环，找到所有唯一的元素，从总和中减去它们，然后计算它们的数量。

剩余的总和是多次出现的所有元素的总和，从数组长度中减去唯一元素的计数得到匹配元素的数量。

相关内容

最新更新

热门标签：