Може да направи аритметичка прогресија од решението за лак код за низи


Ниво на тешкотија Лесно
Често прашувано во Амазон
Низа Сортирање

Проблем изјава

Во проблемот „Може да направи аритметичка прогресија од низа“ ни е дадена низа, сега треба да одговориме дали е можно да се генерира Аритметичка прогресија со преуредување на низата.

пример

arr = [3,1,5]
true

објаснување: Можеме да ја преуредиме низата како {1,3,5} што формира аритметичка прогресија со заедничка разлика како 2, па излезот е точен.

Пристап кон може да се направи аритметичка прогресија од решението за лак код за низи

Аритметичка серија е серија во која разликата помеѓу соседниот број е постојана. Многу основен пристап ќе биде сортирање на низата и проверка на разликата помеѓу соседните елементи, Ако разликата е иста за сите последователни парови, тогаш тоа е аритметичка прогресија, во спротивно не е аритметичка прогресија.

Може да направи аритметичка прогресија од решението за лак код за низи

Временската комплексност за сортирање е позната. Можеме да ја подобриме сложеноста на времето со создавање табела за пребарување на низата.

Н-тиот термин на АП е = a + (n-1) * d, каде што a е првиот елемент од серијата, n е бројот на елементи и d е заедничка разлика.

минималниот елемент на АП е = а и

максималниот елемент на АП е = a + (n-1) * d така

d = (максимум-минимум) / (n-1).

  1. Findе ги најдеме минималните и максималните елементи на низата. Користејќи го, можеме да пресметаме d (заедничка разлика).
  2. Направете табела за пребарување за низата.
  3. Сега го знаеме првиот елемент и заедничката разлика.
  4. Willе провериме дали сите n елементи од аритметичката серија формирани со a и d се присутни во табелата за пребарување.
  5. Ако сите елементи се присутни во табелата за пребарување, тогаш можеме да ја направиме аритметичката прогресија од низата, не можеме да ја направиме аритметичката прогресија од низата.

Имплементација

C ++ код за може да направи аритметичка прогресија од низата

#include <bits/stdc++.h> 
using namespace std; 
  bool canMakeArithmeticProgression(vector<int>& arr) {
  unordered_set<int> seen;
  int mi = INT_MAX, mx = INT_MIN, n = arr.size();
        for (int a : arr) {
            mi = min(mi, a);
            mx = max(mx, a);
            seen.insert(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (seen.find(mi)==seen.end()) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
int main() 
{ 
 vector<int> arr = {3,5,1}; 
 cout <<boolalpha;   
 cout<<canMakeArithmeticProgression(arr)<<endl; 
 return 0;
}
true

Јава код за може да направи аритметичка прогресија од низата

import java.util.*; 
public class Tutorialcup {
 public static boolean canMakeArithmeticProgression(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE, n = arr.length;
        for (int a : arr) {
            mi = Math.min(mi, a);
            mx = Math.max(mx, a);
            seen.add(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (!seen.contains(mi)) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
  public static void main(String[] args) {
    int [] arr = {3,5,1}; 
    System.out.println( canMakeArithmeticProgression(arr));
  }
}
true

Анализа на комплексноста на може да направи аритметичка прогресија од решението на лак кодови за низи

Временска сложеност

Временската сложеност на горенаведениот код е Тој) затоа што ја прелистуваме низата за да создадеме табела за пребарување и проверуваме дали сите елементи од аритметичката серија се присутни во табелата за пребарување. Тука n е големината на влезната низа.

Комплексноста на просторот

Комплексноста на просторот на горенаведениот код е Тој) затоа што создаваме табела за пребарување за низата. Тука n е големината на влезната низа.

Референци