Կարող է թվաբանական առաջընթաց ապահովել հաջորդականության Leetcode լուծումից


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
Դասավորություն դասավորում

Խնդրի հայտարարություն

«Կարող է թվաբանական առաջընթացը կատարել հաջորդականությունից» խնդրի մեջ մեզ տրված է զանգված, այժմ մենք պետք է պատասխանենք, եթե հնարավոր է առաջացնել Թվաբանական առաջընթաց հաջորդականությունը վերադասավորելով:

Օրինակ

arr = [3,1,5]
true

Բացատրությունը. Մենք կարող ենք զանգվածը վերադասավորել որպես {1,3,5}, որը կազմում է թվաբանական առաջընթաց `ընդհանուր տարբերությամբ 2-ով, ուստի ելքը ճիշտ է:

Leetcode- ի հաջորդականության լուծումից կարող է թվաբանական առաջընթաց ապահովել

Թվաբանական շարքը մի շարք է, որի հարակից թվի տարբերությունը հաստատուն է: Շատ հիմնական մոտեցում կլինի զանգվածը տեսակավորելը և հարակից տարրերի տարբերությունը ստուգելը: Եթե բոլոր տարբեր հաջորդական զույգերի համար տարբերությունը նույնն է, ապա դա թվաբանական առաջընթաց է, այլապես թվաբանական առաջընթաց չէ:

Կարող է թվաբանական առաջընթաց ապահովել հաջորդականության Leetcode լուծումից

Տեսակավորման ժամանակի բարդությունը հայտնի չէ: Մենք կարող ենք բարելավել ժամանակի բարդությունը ՝ ստեղծելով զանգվածի որոնման աղյուսակ:

AP- ի n- րդ տերմինը = a + (n-1) * d է, որտեղ a- ն շարքի առաջին տարրն է, n - տարրերի քանակը և d- ը ընդհանուր տարբերություն:

AP- ի նվազագույն տարրը = a և

AP- ի առավելագույն տարրը = a + (n-1) * d so

d = (առավելագույն-նվազագույն) / (n-1):

  1. Մենք կգտնենք զանգվածի նվազագույն և առավելագույն տարրերը: Դրանից օգտվելով մենք կարող ենք հաշվարկել d (ընդհանուր տարբերություն):
  2. Makeանգվածի համար կազմեք որոնման աղյուսակ:
  3. Այժմ մենք գիտենք առաջին տարրը և ընդհանուր տարբերությունը:
  4. Մենք ստուգելու ենք, արդյոք a և d ձևով կազմված թվաբանական շարքի բոլոր n տարրերը առկա են որոնման աղյուսակում:
  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

Java- ի կոդը հաջորդականությունից կարող է կատարել թվաբանական առաջընթաց

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

Բարդության վերլուծությունը կարող է թվաբանական առաջընթաց ապահովել հաջորդականության Leetcode լուծումից

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք անցնում ենք զանգվածը ՝ որոնման աղյուսակ ստեղծելու համար և ստուգում ենք, արդյոք թվաբանական շարքի բոլոր տարրերը առկա են որոնման աղյուսակում: Այստեղ n - մուտքային զանգվածի չափը:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է O (n) քանի որ մենք զանգվածի համար ստեղծում ենք որոնման աղյուսակ: Այստեղ n - մուտքային զանգվածի չափը:

Սայլակ