Easy
,Array
,Sorting
1502. Can Make Arithmetic Progression From Sequence
A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.
Given an array of numbers arr
, 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:
arr.length
<= 1000arr[i]
<= 106
public bool CanMakeArithmeticProgression(int[] arr) {
Array.Sort(arr);
for(int i = arr.Length - 1; i >= 2; i--){
if(arr[i] - arr[i - 1] != arr[1] - arr[0]){
return false;
}
}
return true;
}
JimJun 6, 2023
class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
ios_base::sync_with_stdio(0), cin.tie(0);
int n = arr.size();
if (n == 2) {
return true;
}
sort(arr.begin(), arr.end());
int commonDiff = arr[0] - arr[1];
for (int i = 1; i < n - 1; i ++) {
if (arr[i] - arr[i + 1] != commonDiff) {
return false;
}
}
return true;
}
};
Jerry Wu6 June, 2023
function canMakeArithmeticProgression(arr) {
arr.sort((a, b) => a - b);
const r = arr[1] - arr[0];
for (let i = 2; i < arr.length; i++) {
if (arr[i] - arr[i - 1] !== r) return false;
}
return true;
}
Marsgoat6 June, 2023
看解答看到
function canMakeArithmeticProgression2(arr) {
const min = Math.min(...arr);
const max = Math.max(...arr);
const n = arr.length;
const r = (max - min) / (n - 1); // 找到公差
const set = new Set(arr);
if (r === 0) return true;
if (r % 1 !== 0) return false;
for (let i = 0; i < n; i++) {
if (!set.has(min + i * r)) return false;
}
return true;
}
Marsgoat6 June, 2023
class Solution:
def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
arr = sorted(arr)
r = arr[1] - arr[0]
for i in range(2, len(arr)):
if arr[i] - arr[i-1] != r:
return False
return True
class Solution:
def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
mn, mx = min(arr), max(arr)
n = len(arr)
if mx - mn == 0:
return True
if (mx - mn) % (n - 1):
return False
r = (mx - mn) // (n - 1) # 算公差
st = set()
for num in arr:
if (num - mn) % r:
return False
st.add(num)
return len(st) == n
仿照上面公差的寫法
TC:
SC:
Ron ChenTue, June 7, 2023
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
Arrays.sort(arr);
int r = arr[1] - arr[0];
for(int i = 2; i < arr.length; i++) {
if(arr[i] - arr[i-1] != r)
return false;
}
return true;
}
}
class Solution {
public boolean canMakeArithmeticProgression(int[] arr) {
int min = Arrays.stream(arr).min().getAsInt();
int max = Arrays.stream(arr).max().getAsInt();
int n = arr.length;
if(max - min == 0)
return true;
if((max - min) % (n - 1) != 0)
return false;
int r = (max - min) / (n - 1);
Set<Integer> set = new HashSet<>();
for(int num : arr) {
if((num - min) % r != 0)
return false;
set.add(num);
}
return set.size() == n;
}
}
仿照上面公差的寫法
TC:
SC:
Ron ChenTue, June 7, 2023