How to Find the Missing Number In Arithmetic Progression?
- 时间:2020-09-18 17:01:02
- 分类:网络文摘
- 阅读:96 次
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^5Hints:
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) —
推荐阅读:小东的爷爷积攒了5000元钱打算存入银行 绿地长24米,宽15米,中间有宽为2米的道路 一群兔子在一块地里拔萝卜 学校组织春游,组了几条船让学生们划 三个人平均分一包糖,没有剩余 商店同时卖出两件上衣,每件售价均为120 正方形的面积是8平方米,求阴影图形面积 求阴影面积(有扇形有半圆) “六一”儿童节作文700字 习惯与责任作文
- 评论列表
-
- 添加评论