java 解决 Codility 的 PermMissingElem 测试的正确方法是什么？(爪哇)

What is the right way to solve Codility's PermMissingElem test? (Java)

提问by steelmonkey

I have the following problem taken from Codility's code testing exercises:

我从 Codility 的代码测试练习中遇到了以下问题：

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

给出了一个由 N 个不同整数组成的零索引数组 A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着恰好缺少一个元素。

Your goal is to find that missing element.

你的目标是找到那个缺失的元素。

Write a function:

写一个函数：

class Solution { public int solution(int[] A); }

类解决方案{ public int 解决方案(int[] A); }

that, given a zero-indexed array A, returns the value of the missing element.

给定一个零索引数组 A，返回缺失元素的值。

For example, given array A such that:

例如，给定数组 A 使得：

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

the function should return 4, as it is the missing element.

该函数应返回 4，因为它是缺失的元素。

Assume that:

假使，假设：

N is an integer within the range [0..100,000]; the elements of A are all distinct; each element of array A is an integer within the range [1..(N + 1)].

N是[0..100,000]范围内的整数；A 的元素都是不同的；数组 A 的每个元素都是 [1..(N + 1)] 范围内的整数。

Complexity:

复杂：

expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not >counting the storage required for input arguments).

预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(1)，超出输入存储（不计算输入参数所需的存储）。

Elements of input arrays can be modified.

可以修改输入数组的元素。

---

---

My approach was to convert the given array into an ArrayList, use the ArrayList to find the lowest and highest values inside the array, and iterate through all possible values from lowest to highest, and then return the missing value.

我的做法是将给定的数组转换成一个ArrayList，使用ArrayList找出数组内的最低和最高值，从最低到最高遍历所有可能的值，然后返回缺失的值。

This solves the example problem, but my problem seems to be that I cannot get right answers under the following conditions of the given array:

这解决了示例问题，但我的问题似乎是在给定数组的以下条件下我无法得到正确答案：

"empty list and single element"

"the first or the last element is missing"

"single element"

"two elements"

“空列表和单个元素”

“缺少第一个或最后一个元素”

“单一元素”

“两个要素”

What am I doing wrong, and what is the proper way to go about solving this problem?

我做错了什么，解决这个问题的正确方法是什么？

回答by PM 77-1

This problem has a mathematical solution, based on the fact that the sum of consecutive integers from 1 to n is equal to n(n+1)/2.

这个问题有一个数学解决方案，基于这样一个事实，即从 1 到 n 的连续整数n(n+1)/2之和等于。

Using this formula we can calculate the sum from 1 to N+1. Then with O(N)time complexity we calculate the actual sum of all elements in the array.

使用这个公式，我们可以从 计算总和1 to N+1。然后用O(N)时间复杂度计算数组中所有元素的实际总和。

The difference between the full and actual totals will yield the value of the missing element.

完整总数和实际总数之间的差异将产生缺失元素的值。

Space complexity is O(1).

空间复杂度为O(1)。

回答by BuZz

Another 100% solution:

另一个 100% 解决方案：

There is actually not even a need to use 64-bit integers to avoid the overflows that a couple of tests try to trigger (the ones with array size of 100000 at the time of writing). And you can get away with only one sum variable. The last line avoids overflows further by implementing n(n+1)/2 differently so that the division by two occurs "early":

实际上甚至不需要使用 64 位整数来避免一些测试试图触发的溢出（在撰写本文时数组大小为 100000 的那些）。而且您可以只使用一个 sum 变量。最后一行通过以不同方式实现 n(n+1)/2 来进一步避免溢出，以便“早期”发生除以二：

C#: class Solution { public int solution(int[] A) { var sum = 0; for(int i = 0; i < A.Length; i++) sum += A[i];
return A.Length % 2 == 0 ? -sum + (A.Length/2 + 1) * (A.Length+1) : -sum + (A.Length/2 + 1) * (A.Length+2); } }

C＃： class Solution { public int solution(int[] A) { var sum = 0; for(int i = 0; i < A.Length; i++) sum += A[i];
return A.Length % 2 == 0 ? -sum + (A.Length/2 + 1) * (A.Length+1) : -sum + (A.Length/2 + 1) * (A.Length+2); } }

回答by RobyB

This problem is part of the Lessons of Time Complexity.

这个问题是时间复杂性课程的一部分。

https://codility.com/media/train/1-TimeComplexity.pdf

https://codility.com/media/train/1-TimeComplexity.pdf

In fact at the end there is the explanation on how to compute the sum of the elements in an array, without do any loop.

事实上，最后有关于如何计算数组中元素的总和的解释，而无需进行任何循环。

This is the final solution in Python3:

这是 Python3 中的最终解决方案：

def solution(A):

    n = len(A)+1
    result = n * (n + 1)//2

    return result - sum(A)

回答by presto8

The problem statement clearly specifies that the array will consist of "N different integers", thus N must be at least 2. N=0 and N=1 simply do not make sense if we write them in English, e.g. "An array consisting of 0 different integers...".

问题陈述清楚地指定数组将由“N 个不同的整数”组成，因此 N 必须至少为 2。如果我们用英文写 N=0 和 N=1，它们根本没有意义，例如“一个由以下组成的数组” 0 个不同的整数...”。

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

给出了一个由 N 个不同整数组成的零索引数组 A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着恰好缺少一个元素。

With these initial conditions and stated assumptions, tests like "single element", "empty list", etc., are completely inappropriate.

有了这些初始条件和陈述的假设，像“单个元素”、“空列表”等测试是完全不合适的。

Proper production code would most likely have to test for invalid conditions, but that wasn't a stated goal of the challenge.

正确的生产代码很可能必须测试无效条件，但这并不是挑战的既定目标。

回答by Iryna Prokopenko

my solution in java 100% Detected time complexity: O(N)

我在 Java 中的解决方案 100% 检测到的时间复杂度：O(N)

import java.util.*;

class Solution {
public int solution(int[] arr) {

    if(arr.length == 0) return 1;

    int sumArr = 0;


    for(int i=0; i < arr.length; i++){

        sumArr = sumArr + arr[i];

    }


    int sumN = 0;

     for(int i=1; i <= arr.length+1; i++){

        sumN = sumN + i;

    }


    if(sumArr == sumN)  return arr.length;


    return  sumN - sumArr;
}

}

}

回答by Ashish

You can use an Array to sort the element first and then use simple for loop to iterate over it, and find the missing value. Here is my simple code with detected time complexity of O(N)or O(N * log(N))in codility.

您可以先使用 Array 对元素进行排序，然后使用简单的 for 循环对其进行迭代，并找到缺失值。这是我的简单代码，检测到的时间复杂度为O(N)或O(N * log(N))在编码中。

public static int solution(int[] A) {

    int size = A.length;
    int count = 1;

    Arrays.sort(A);

    for (int i = 0; i < size; i++) {
        if (A[i] != count)
            return count;
        count++;
    }
    return count;
}

回答by Josep Vidal

Here is the solution in PHP using the sum of consecutive integers from 1 to n is equal to n(n+1)/2.

这是 PHP 中使用从 1 到 n 的连续整数之和等于 n(n+1)/2 的解决方案。

function solution($A) {

    $size = count($A) + 1;
    $total = ($size * ($size + 1)) / 2;

    return  $total - array_sum($A);

}

回答by Yuvaraj Ram

private static int getMissingElementInArrayNew(int[] A) throws IOException {
        double n =  A.length + 1;
        double totalSum = (double) ((n * (n + 1)) / 2);

        for (int i = 0; i < A.length; i++) {
            totalSum -= A[i];
        }

        return (int) (totalSum == 0 ? A.length + 1 : totalSum); 
    }

回答by Chigozie Orunta

Here's another solution using JavaScript tested 100%.

这是使用 JavaScript 100% 测试的另一个解决方案。

function solution(A) {
    let maximumNumber = A.length + 1;
    let totalSum = (maximumNumber*(maximumNumber + 1))/2;
    let partialSum = 0;
    for(let i=0; i<A.length; i++) {
        partialSum += A[i];
    }
    return totalSum - partialSum;
}

回答by Luke Hamilton

Golang solution:

Golang解决方案：

func Solution(A []int) int {
  n := len(A) + 1
  total := n * (n + 1) /2
  for _, e := range A {
    total -= e
  }
  return total
}