រកលេខគត់ដែលមិនមានតែមួយគត់បូករហូតដល់សូន្យ Leetcode ដំណោះស្រាយ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon Facebook ក្រុមហ៊ុន Microsoft
អារេ

បញ្ហារកឃើញលេខគត់ដែលមានតែមួយគត់បូករហូតដល់សូន្យ Leetcode ដំណោះស្រាយផ្តល់ឱ្យយើងនូវចំនួនគត់។ វាស្នើសុំឱ្យយើងប្រគល់លេខគត់ដែលមានតែមួយគត់ដែលបូកដល់ ០ ។ ដូច្នេះសំណួរគឺងាយយល់ណាស់។ ដូច្នេះមុននឹងមុជចូលក្នុងដំណោះស្រាយ។ ចូរយើងពិចារណាឧទាហរណ៍ខ្លះ។

រកលេខគត់ដែលមិនមានតែមួយគត់បូករហូតដល់សូន្យ Leetcode ដំណោះស្រាយ

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

ការពន្យល់ៈវាអាចមានលទ្ធផលជាច្រើនចំពោះបញ្ហា។ ប៉ុន្តែសូមឱ្យយើងយកលទ្ធផលដែលបានផ្តល់ឱ្យ។ រាល់ចំនួនគត់នៅក្នុងលទ្ធផលគឺមានតែមួយ។ ដូច្នេះការបំពេញលក្ខខណ្ឌដែលបានដាក់និងផលបូកនៃចំនួនគត់ដែលបានផ្តល់គឺ ០ ។ ហេតុដូច្នេះលក្ខខណ្ឌទាំងពីរត្រូវបានពេញចិត្ត។

n = 3
[-1, 0, 1]

ការពន្យល់៖ លទ្ធផលដែលបានផ្តល់មានចំនួនគត់ដែលខុសប្លែកពីគេហើយផលបូករបស់វាគឺ ០ ផងដែរ។

វិធីសាស្រ្តសម្រាប់ការរកឃើញលេខគត់តែមួយគត់បូករហូតដល់សូន្យ Leetcode ដំណោះស្រាយ

វិធីសាស្រ្តសម្រាប់បញ្ហាគឺភាគច្រើននៃពេលវេលាគឺការបង្ក្រាបលំនាំ។ វាតែងតែមានគំរូមូលដ្ឋាននៅក្នុងសំណួរទាំងនេះ។ ដូច្នេះនៅពេលណាដែលយើងព្យាយាមស្វែងរកគំរូសម្រាប់សំណួរ។ តែងតែព្យាយាមរកចម្លើយសម្រាប់តម្លៃតូចជាងមុននៃ n បន្ទាប់មកព្យាយាមរកគំរូ។ សម្រាប់ n = 1 លទ្ធផលអាចជា 0 ។ ចំពោះ n = 2 លទ្ធផលអាចជា [-1, 1] ។ ស្រដៀងគ្នាសម្រាប់ n = 3, លទ្ធផលអាចជា [-2, 0, 2], សម្រាប់ n = 4, ទិន្នផលអាចជា [-3, -1, 1, 3] ។ ដូច្នេះយើងឃើញគំរូមួយដែលលទ្ធផលបង្កើតជា AP ដែលប្រសិនបើតម្លៃ n គឺសេស។ ធាតុកណ្តាលគឺ ០ ប្រសិនបើតម្លៃនៃ n គឺសូម្បីតែពេលនោះធាតុ (n + ១) / ២ គឺ ១ ។ ដូច្នេះដោយប្រើព័ត៌មាននេះយើងអាចបង្កើតរូបមន្ត។ រូបមន្តអាចជា [i] = 0 * i + 1-n ។ ឥឡូវយើងគ្រាន់តែប្រើរូបមន្តនេះដើម្បីបំពេញធាតុ n នៃឯកសារ អារេ.

លេខកូដដើម្បីស្វែងរកលេខគត់ដែលមិនមានតែមួយបូកបញ្ចូលគ្នារហូតដល់សូន្យ Leetcode ដំណោះស្រាយ

លេខកូដ 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 (N), ដោយសារយើងគ្រាន់តែបំពេញអារេហើយធាតុនីមួយៗអាចត្រូវបានគណនា ឱ (១)។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

O (N), ពីព្រោះយើងបង្កើតអារេមួយដែលត្រូវត្រលប់មកវិញជាលទ្ធផល។