تعداد N عدد صحیح منحصر به فرد را تا Solution Leetcode Solution پیدا کنید


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

مسئله Find N Unique Integers Sum تا Zero Leetcode Solution ، یک عدد صحیح را برای ما فراهم می کند. این از ما می خواهد که n عدد صحیح منحصر به فرد را جمع کنیم که جمعاً 0 باشد. بنابراین ، درک این سوال بسیار ساده است. بنابراین ، قبل از شیرجه رفتن در محلول. اجازه دهید نگاهی به چند نمونه بیندازیم.

تعداد N عدد صحیح منحصر به فرد را تا Solution Leetcode Solution پیدا کنید

n = 5
[-7,-1,1,3,4]

توضیح: خوب ، چندین خروجی برای مسئله وجود دارد. اما اجازه دهید ما خروجی داده شده را بگیریم. تمام اعداد صحیح در خروجی منحصر به فرد هستند. بنابراین تأمین شرط تحمیل شده و مجموع تمام عدد صحیح داده شده 0 است. از این رو ، هر دو شرط راضی هستند.

n = 3
[-1, 0, 1]

توضیح: خروجی داده شده تمام عددهای صحیح منحصر به فرد را دارد و مجموع آنها نیز 0 است. بنابراین ، خروجی همه شرایط تحمیل شده را برآورده می کند.

رویکردی برای یافتن N عدد صحیح منحصر به فرد تا راه حل صفر Leetcode

رویکرد برای مشکلات در بیشتر مواقع شکستن الگو است. در این نوع س alwaysالات همیشه برخی از الگوهای اساسی وجود دارد. بنابراین ، هر زمان که سعی کنیم الگوی یک سوال را پیدا کنیم. همیشه سعی کنید جواب مقادیر کوچکتر n را پیدا کنید ، سپس سعی کنید الگو را پیدا کنید. برای n = 1 ، خروجی می تواند 0 باشد. برای n = 2 ، خروجی می تواند [-1 ، 1] باشد. به طور مشابه برای n = 3 ، خروجی می تواند [-2 ، 0 ، 2] باشد ، برای n = 4 ، خروجی می تواند [-3 ، -1 ، 1 ، 3] باشد. بنابراین ، الگویی را مشاهده می کنیم که در صورت خروجی ، AP مقدار AP را تشکیل می دهد اگر مقدار n عجیب باشد. عنصر میانی 0 است. اگر مقدار n برابر باشد ، عنصر (n + 1) / 2 برابر 1 است. بنابراین ، با استفاده از این اطلاعات ، می توان فرمولی را ابداع کرد. فرمول می تواند [i] = 2 * i + 1-n باشد. اکنون ، ما به راحتی از این فرمول برای پر کردن عناصر n استفاده می کنیم صف.

کد را برای یافتن N عدد صحیح منحصر به فرد جمع کنید تا Solution Leetcode Solution

کد C ++

#include <bits/stdc++.h>
using namespace std;

vector<int> sumZero(int n) {
    vector<int> v(n);
    for(int i=0;i<n;i++)
        v[i] = 2*i - n + 1;
    return v;
}

int main(){
    vector<int> output = sumZero(7);
    for(auto x: output)
        cout<<x<<" ";
}
-6 -4 -2 0 2 4 6

کد جاوا

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
    public static int[] sumZero(int n) {
        int[] v = new int[n];
        for(int i=0;i<n;i++)
            v[i]= 2*i - n + 1;
        return v;
    }
    
    public static void main(String[] args){
    	int[] output = sumZero(7);
    	for(int i=0;i<7;i++)
    		System.out.print(output[i]+" ");
    }
}
-6 -4 -2 0 2 4 6

تحلیل پیچیدگی

پیچیدگی زمان

بر)، از آنجا که ما به راحتی آرایه را پر می کنیم و می توان هر عنصر را در آن محاسبه کرد O (1). بنابراین ، پیچیدگی زمان خطی است.

پیچیدگی فضا

بر)، زیرا ما یک آرایه ایجاد می کنیم که باید به عنوان خروجی برگردانده شود.