LeetCode 1228 - Missing Number In Arithmetic Progression

https://www.geeksforgeeks.org/find-missing-number-arithmetic-progression/

Given an array that represents elements of arithmetic progression in order. One element is missing in the progression, find the missing number.

Examples:

Input: arr[]  = {2, 4, 8, 10, 12, 14}
Output: 6

Input: arr[]  = {1, 6, 11, 16, 21, 31};
Output: 26

static int findMissingUtil(int arr[], int low, 

                           int high, int diff)

{

    // There must be two elements

    // to find the missing

    if (high <= low)

        return Integer.MAX_VALUE;

  

    // Find index of 

    // middle element

    int mid = low + (high - low) / 2;

  

    // The element just after the 

    // middle element is missing. 

    // The arr[mid+1] must exist, 

    // because we return when

    // (low == high) and take

    // floor of (high-low)/2

    if (arr[mid + 1] - arr[mid] != diff)

        return (arr[mid] + diff);

  

    // The element just 

    // before mid is missing

    if (mid > 0 && arr[mid] - 

                   arr[mid - 1] != diff)

        return (arr[mid - 1] + diff);

  

    // If the elements till mid follow 

    // AP, then recur for right half

    if (arr[mid] == arr[0] + mid * diff)

        return findMissingUtil(arr, mid + 1, 

                               high, diff);

  

    // Else recur for left half

    return findMissingUtil(arr, low, mid - 1, diff);

}

  

// The function uses findMissingUtil() 

// to find the missing element in AP. 

// It assumes that there is exactly 

// one missing element and may give 

// incorrect result when there is no 

// missing element or more than one

// missing elements. This function also 

// assumes that the difference in AP is

// an integer.

static int findMissing(int arr[], int n)

{

    // If exactly one element is missing, 

    // then we can find difference of

    // arithmetic progression using 

    // following formula. Example, 2, 4, 

    // 6, 10, diff = (10-2)/4 = 2.

    // The assumption in formula is that 

    // the difference is an integer.

    int diff = (arr[n - 1] - arr[0]) / n;

  

    // Binary search for the missing 

    // number using above calculated diff

    return findMissingUtil(arr, 0, n - 1, diff);

}




https://www.acwing.com/solution/LeetCode/content/5441/

数组 arr 中的值符合等差数列的数值规律：在 0 <= i < arr.length - 1 的前提下，arr[i+1] - arr[i] 的值都相等。

然后，我们从数组中删去一个 既不是第一个也不是最后一个的值。

给你一个缺失值的数组，请你帮忙找出那个被删去的数字。

样例

输入：arr = [5,7,11,13]
输出：9
解释：原来的数组是 [5,7,9,11,13]。

输入：arr = [15,13,12]
输出：14
解释：原来的数组是 [15,14,13,12]。

限制

• 3 <= arr.length <= 1000
• 0 <= arr[i] <= 10^5

(暴力枚举) $O(n)$

1. 首先求出 arr[1] - arr[0] 与 arr[n - 1] - arr[n - 2] 的差值 diff1 和 diff2。
2. 如果这两个差值不相等，若 diff1 == 2 * diff2，则缺失的值为 arr[0] + diff2；若 diff2 == 2 * diff1 则缺失的值为 arr[n - 1] - diff1。
3. 如果这两个差值相等，则说明差值就是 diff1（或 diff2），遍历一次数组，找到相邻两个元素不等的时候返回答案。
4. 如果没有找到，说明整个数组值全部相等，则直接返回 arr[0]。

时间复杂度

• 最多遍历一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 只需常数的额外空间。

int missingNumber(vector<int>& arr) { int n = arr.size(); int diff1 = arr[1] - arr[0]; int diff2 = arr[n - 1] - arr[n - 2]; if (diff1 != diff2) { if (diff1 == 2 * diff2) return arr[0] + diff2; else return arr[n - 1] - diff1; } for (int i = 1; i < n - 2; i++) if (arr[i + 1] - arr[i] != diff1) return arr[i] + diff1; return arr[0]; },

X.
https://www.codeleading.com/article/15242380716/

两个tricky的地方：

• 负数的整除不是truncate。（-3）//2 = -2 WHAT？？？
• 输入可以是同样的数，这样把任意一个同样的数可以补在任何的位置。所以result要赋值为arr【0】

def missingNumber(self, arr: List[int]) -> int: if arr[-1] > arr[0]: step = (arr[-1] - arr[0])//len(arr) else: step = (arr[0] - arr[-1])//len(arr) * -1 # tricky place 1。当然这里应该是整除的。 result = arr[0] # tricky place 2 for i in range(1, len(arr)): if arr[i] - arr[i-1] != step: result = arr[i-1] + step break return result

https://www.icode9.com/content-4-519698.html

• 1. 通过首尾元素算出该等差序列的差值, (tail-first)/len
• 1. 使用为2的窗口扫描整个数组, 选出前后两元素差值不等于之前整体差值的前一个元素
• 1. 输出前一个元素+差值

代码实现

暴力法 使用窗口遍历整个数组

class Solution {
    public int missingNumber(int[] arr) {
        int len = arr.length;
        // first, last 首尾两元素
        int first = arr[0], last = arr[len-1];
        // 该等差序列的整体等差
        int sub = (last-first) / len;

        for (int i = 0; i < len-1; i++) {
            // 一个为2的窗口 [i, i+1]
            int cur = arr[i], next = arr[i+1];
            // System.out.printf("cur:%d next:%d n1:%d\n", cur, next, cur+sub);
            // 如何前后元素差值不为等差, 那么前一个元素+等差 就是缺失的元素
            if (cur+sub != next) {
                return cur+sub;
            }
        }

        return 0;
    }

X. NlogN
https://www.cnblogs.com/seyjs/p/11713478.html

解题思路：题目很简单。先对数组排序，根据最大值和最小值即可求出公差，然后遍历数组，计算相邻元素的差，如果差不等于公差，即表示数字缺失。

    def missingNumber(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        arr.sort()
        diff = (arr[-1] - arr[0])/(len(arr))
        for i in range(len(arr)-1):
            if arr[i] + diff != arr[i+1]:
                return arr[i] + diff
        return arr[0]