How to Find the Missing Number In Arithmetic Progression?

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

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) —

推荐阅读:
学校买羽毛球和乒乓球共花了100元  一批游客过河:如果每只船坐10人  两个扇形一个长方形求阴影面积  初中的友谊,初中的开始  海景作文300字  妈妈的生日  民族的精魂  茅田山作文  “六一”游园活动作文  那一次,我真尴尬 
评论列表
添加评论