می تواند از راه حل کد توالی ، حسابی پیشرفت کند


سطح دشواری ساده
اغلب در آمازون
صف مرتب سازی

بیان مسأله

در مسئله ”Can make Arritmetic Progress From Sequence” به ما یک آرایه داده می شود ، اکنون ما باید در صورت امکان تولید یک پاسخ دهیم. پیشرفت حسابی با تنظیم مجدد توالی.

مثال

arr = [3,1,5]
true

شرح: می توانیم آرایه را به صورت {1,3,5،2،XNUMX} تنظیم کنیم که یک پیشرفت حسابی را با یک تفاوت مشترک به عنوان XNUMX تشکیل می دهد ، بنابراین خروجی درست است.

رویکرد برای پیشرفت محاسباتی می تواند از محلول Sequence Leetcode ایجاد کند

سری حسابی سری است که در آن اختلاف بین عدد مجاور ثابت است. یک روش اساسی این است که آرایه مرتب شود و تفاوت بین عناصر مجاور بررسی شود ، اگر تفاوت برای همه جفتهای متوالی یکسان باشد ، این یک پیشرفت حسابی است در غیر این صورت یک پیشرفت حسابی نیست.

می تواند از راه حل کد توالی ، حسابی پیشرفت کند

پیچیدگی زمان برای مرتب سازی nlogn است. می توانیم با ایجاد یک جدول جستجو برای آرایه ، پیچیدگی زمان را بهبود ببخشیم.

نهمین عبارت AP = a + (n-1) * d است ، جایی که a اولین عنصر مجموعه است ، n تعداد عناصر و d تفاوت مشترک است.

حداقل عنصر AP = a و

حداکثر عنصر AP = a + (n-1) * d بنابراین است

d = (حداکثر-حداقل) / (n-1).

  1. حداقل و حداکثر عناصر آرایه را پیدا خواهیم کرد. با استفاده از آن می توان d (اختلاف مشترک) را محاسبه کرد.
  2. یک جدول جستجو برای آرایه ایجاد کنید.
  3. اکنون اولین عنصر و تفاوت مشترک را می دانیم.
  4. ما بررسی خواهیم کرد که آیا همه n عناصر سری حسابهای تشکیل شده توسط a و d در جدول جستجو وجود دارد.
  5. اگر همه عناصر در جدول جستجو وجود داشته باشد ، می توانیم از ترتیب دنباله ای حساب کنیم ، در غیر این صورت نمی توانیم از دنباله پیشرفت حساب را انجام دهیم.

پیاده سازی

کد ++ C برای Can Can Arithmetic Progress From Sequence

#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

کد جاوا برای Can Can Arithmetic Progress From Sequence

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

پیچیدگی زمانی

پیچیدگی زمانی کد فوق است O (N) زیرا ما در حال مرور آرایه برای ایجاد یک جدول جستجو هستیم و بررسی می کنیم که آیا همه عناصر سری حساب در جدول مراجعه وجود دارد. در اینجا n اندازه آرایه ورودی است.

پیچیدگی فضا

پیچیدگی فضایی کد فوق است O (N) زیرا ما در حال ایجاد یک جدول جستجو برای آرایه هستیم. در اینجا n اندازه آرایه ورودی است.

منابع