Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.
Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.
Example 1:
Input: arr = [3,5,1] Output: true Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.
Example 2:
Input: arr = [1,2,4] Output: false Explanation: There is no way to reorder the elements to obtain an arithmetic progression.
Constraints:
2 <= arr.length <= 1000-10^6 <= arr[i] <= 10^6
Solution 1: Sort and check.
Time complexity: O(nlog)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: bool canMakeArithmeticProgression(vector<int>& arr) { sort(begin(arr), end(arr)); const int diff = arr[1] - arr[0]; for (int i = 2; i < arr.size(); ++i) if (arr[i] - arr[i - 1] != diff) return false; return true; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public boolean canMakeArithmeticProgression(int[] arr) { Arrays.sort(arr); int diff = arr[1] - arr[0]; for (int i = 2; i < arr.length; ++i) if (arr[i] - arr[i - 1] != diff) return false; return true; } } |
python3
|
1 2 3 4 5 |
class Solution: def canMakeArithmeticProgression(self, arr: List[int]) -> bool: arr.sort() diff = arr[1] - arr[0] return all(i - j == diff for i, j in zip(arr[1:], arr[:-1])) |
Solution 2: Rearrange the array
Find min / max / diff and put each element into its correct position by swapping elements in place.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: bool canMakeArithmeticProgression(vector<int>& arr) { const int n = arr.size(); const auto [loit, hiit] = minmax_element(cbegin(arr), cend(arr)); const auto [lo, hi] = pair{*loit, *hiit}; if ((hi - lo) % (n - 1)) return false; const int diff = (hi - lo) / (n - 1); if (diff == 0) return true; for (int i = 0; i < n; ++i) { if ((arr[i] - lo) % diff) return false; const int idx = (arr[i] - lo) / diff; if (idx != i) swap(arr[i--], arr[idx]); } return true; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment