How to Find the Missing Number In Arithmetic Progression?

  • 时间:2020-09-18 17:01:02
  • 分类:网络文摘
  • 阅读:98 次

In some array arr, the values were in arithmetic progression: the values arr[i+1] – arr[i] are all equal for every 0 <= i < arr.length – 1.
Then, a value from arr was removed that was not the first or last value in the array.

Return the removed value.
Example 1:
Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

Example 2:
Input: arr = [15,13,12]
Output: 14
Explanation: The previous array was [15,14,13,12].

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

Hints:
Assume the sequence is increasing, what if we find the largest consecutive difference?
Is the missing element in the middle of the segment with the largest consecutive difference?
For decreasing sequences, just reverse the array and do a similar process.

Finding the Missing Number In Arithmetic Progression in C++

As the first and the last element of the array is not the missed ones, thus we can compute the steps of the Arithmetic Progression. We can convert the numbers into the set, then we check the progressing numbers and return one that is not in the set. This requires O(N) space and O(N) time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int d = (arr.back() - arr[0]) / (int)arr.size();
        if (d == 0) return arr[0];
        unordered_set s(begin(arr), end(arr));
        for (int i = 0; i < arr.size(); ++ i) {
            int t = (arr[0] + i * d);
            if (!s.count(t)) {
                return t;
            }
        }
        return arr[0];
    }
};
class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int d = (arr.back() - arr[0]) / (int)arr.size();
        if (d == 0) return arr[0];
        unordered_set s(begin(arr), end(arr));
        for (int i = 0; i < arr.size(); ++ i) {
            int t = (arr[0] + i * d);
            if (!s.count(t)) {
                return t;
            }
        }
        return arr[0];
    }
};

The .size() returns unsigned integer, thus need converting to (int) to get the distance between two numbers in the Arithmetic Progression.

Actually, we don’t need to allocate the set, we can just compare with the numbers in the array. The following C++ code runs O(N) time and uses O(1) constant space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int d = arr.back() - arr[0];
        int s = d / (int)arr.size();
        int t = arr[0];
        for (int i = 1; i < n; ++ i) {
            t += s;
            if (arr[i] != t) {
                return t;
            }
        }
        return arr[0];
    }
};
class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int d = arr.back() - arr[0];
        int s = d / (int)arr.size();
        int t = arr[0];
        for (int i = 1; i < n; ++ i) {
            t += s;
            if (arr[i] != t) {
                return t;
            }
        }
        return arr[0];
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
都是马虎惹的祸作文400字  美中不足  诗酒永相随(文/白水先生)  学习古人的智慧  关于清明节的小作文200字  地震中的父与子500字  二年级作文家乡的水  都是马虎惹得祸作文200字  美味在眼前,我手煮我心  离殇 
评论列表
添加评论