PermMissingElem:
Find the missing element in a given permutation.

An 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.

Your goal is to find that missing element.

Write a function:

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

that, given an array A, returns the value of the missing element.

For example, given array A such that: A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

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

Write an efficient algorithm for the following assumptions:

  • 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)].

這題一開始看錯以為是隨機順序(EX: {100,102,103})，所以寫了一個梯形公式去做加總

public static int permMissingElemAnyNumber(int[] a) {
        if (a.length == 0) {
            return 1;
        }
        long min = a[0], max = 0, missArrSum = 0, len = a.length + 1;
        int noMissCount = 0;
        int j = a[0];
        for (int i : a) {
            if (i == j) {
                j += 1;
                noMissCount++;
            }
            min = Math.min(min, i);
            max = Math.max(max, i);
            missArrSum += i;
        }
        if (min == 0) {
            min = 1;
            len--;
        }
        long normalSum = (min + max) * len / 2;
        if (normalSum <= missArrSum) {
            return 1;
        }
        if (noMissCount == a.length) {
            return a[a.length - 1] + 1;
        }
        return (int) (normalSum - missArrSum);
    }

後來因題目分數都沒到100，才發現原來順序都是從1開始，那從1的加總就換了別的公式，寫起來也更簡單了

public static int permMissingElem(int[] a) {
        long len = a.length;
        if (len == 0) {
            return 1;
        }
        long arrSum = 0, noMissSum;
        for (int i : a) {
            arrSum += i;
        }
        ++len;
        noMissSum = len * (len + 1) / 2;
        return (int) (noMissSum - arrSum);
    }

執行結果 : https://app.codility.com/demo/results/training7UEKHU-XQV/