Leetcode шийдлийг интервал оруулах  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн Facebook-ийн Google-ийн LinkedIn Microsoft- Oracle-ийн ҮйлчилгээNow Twitter Uber
алгоритмууд Array кодлох Датаминр ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions эрэмбэлэх

Insert Interval Leetcode Solution шийдэл нь зарим интервалын жагсаалт болон тусдаа интервалыг бидэнд өгдөг. Дараа нь интервалын жагсаалтад энэ шинэ интервалыг оруулах хэрэгтэй гэж хэлсэн. Тиймээс, шинэ интервал нь жагсаалтад орсон интервалуудтай огтлолцож магадгүй эсвэл үгүй ​​байж магадгүй юм. Хэрэв уулзвар байгаа бол бид интервалыг нэгтгэдэг. Үгүй бол бид интервалын жагсаалтын өсөх дарааллыг дагаж байрлалд оруулна.

Leetcode шийдлийг интервал оруулах

Жишээ нь  

intervals = [[1,3],[6,9]], newInterval = [2,5]
[[1,5],[6,9]]

Тайлбар: Шинэ интервал нь жагсаалтын эхний интервалтай огтлолцоно. Тиймээс шинэ интервалыг эхний интервалтай нэгтгэв. Энэ нь өгөгдсөн гарцаар бидэнд үлдэх болно.

intervals = [], newInterval = [0,5]
[0,5]

Тайлбар: Эхэндээ, жагсаалтад завсарлага байхгүй тул. Бид зүгээр л шинэ интервалыг оруулсан.

Leetcode уусмал оруулах интервал  

Insert Interval Leetcode Solution гэдэг нь бидэнд зарим интервал, оруулах шаардлагатай нэмэлт интервал өгсөн. Тиймээс, гарч болзошгүй боломжуудыг дууриаж чадвал бид асуудлыг шийдэж чадна. Хоёр боломж байна, эсвэл шинэ интервал нь жагсаалтад аль хэдийн орсон зарим интервалтай огтлолцох юмуу эсвэл үгүй. Тиймээс, хэрэв тийм бол бид тэдгээрийг нэгтгэж, өөр байрлалыг тодорхой байрлалд байрлуулна. Тодорхой байрлалаар бид жагсаалтад орсон өсөх дарааллыг оруулсны дараа ч хэвээр хадгална гэсэн үг юм.

мөн үзнэ үү
Бүх жүржийг ялзрахад шаардагдах хамгийн бага хугацаа

Тиймээс үүнийг зохицуулахын тулд бид шинэ вектор үүсгэдэг (массив) векторуудын. Энэ интервалуудыг шинээр үүсгэсэн гаралтын вектор руу оруулж эхэлнэ. Одоогийн интервал оруулах завсартай давхцаж байгаа эсэхийг бид шалгаж байна. Хэрэв тэд үүнийг хийвэл бид давталтаас гарах болно. Давталтын дараа давхардсан элемент нь жагсаалтад байгаа интервалуудын дунд байгаа эсэхийг шалгана. Хэрэв тэдгээр нь давхцаж байвал бид одоогийн интервалыг шинэ интервалтай нэгтгэж, үлдсэн интервалуудыг оруулна. Хэрэв үгүй ​​бол интервалын эхлэх байрлал оруулах интервалын эхлэх байрлалаас бага болтол бид элементүүдийг гаралтын вектор руу оруулна. Дараа нь бид шинэ интервал, дараа нь үлдсэн интервалыг оруулна.

код  

Insert Interval Leetcode Solution-т зориулсан C ++ код

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

bool overlap(vector<int> a, vector<int> b){
    return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
}

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    int i;
    vector<vector<int>> newIntervals;
    for(i=0;i<intervals.size();i++)
        if(overlap(intervals[i], newInterval))
            break;
        else
            newIntervals.push_back(intervals[i]);
    if(i<intervals.size()){
        intervals[i][0] = min(intervals[i][0], newInterval[0]);
        intervals[i][1] = max(intervals[i][1], newInterval[1]);
        newIntervals.push_back(intervals[i]);
        int j = i;
        i++;
        for(;i<intervals.size();i++)
            if(overlap(intervals[j], intervals[i])){
                newIntervals[j][0] = min(newIntervals[j][0], intervals[i][0]);
                newIntervals[j][1] = max(newIntervals[j][1], intervals[i][1]);
            } else
                newIntervals.push_back(intervals[i]);
        return newIntervals;
    }
    for(i=0;i<intervals.size();i++)
        if(newIntervals[i][0]>newInterval[0])
            break;
    newIntervals.insert(newIntervals.begin() + i, newInterval);
    return newIntervals;
}

int main(){
  vector<vector<int>> intervals = {{0,5}};
  vector<int> newInterval = {1,6};
  vector<vector<int>> output = insert(intervals, newInterval);
  for(int i=0;i<output.size();i++)
    cout<<output[i][0]<<" "<<output[i][1];
}
0 6

Insert Interval Leetcode шийдлийн Java код

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

class Solution {
  
    private static boolean overlap(int[] a, int[] b){
        return (a[0] <= b[0] && b[0] <= a[1]) || (b[0] <= a[0] && a[0] <= b[1]);
    }
    
    private static int[][] insert(int[][] intervals, int[] newInterval) {
        int i;
        ArrayList<Integer[]> newIntervals = new ArrayList<Integer[]>();
        for(i=0;i<intervals.length;i++)
            if(overlap(intervals[i], newInterval))
                break;
            else
                newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
        if(i<intervals.length){
            intervals[i][0] = Math.min(intervals[i][0], newInterval[0]);
            intervals[i][1] = Math.max(intervals[i][1], newInterval[1]);
            newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
            int j = i;
            i++;
            for(;i<intervals.length;i++)
                if(overlap(intervals[j], intervals[i])){
                    int a = Math.min(intervals[j][0], intervals[i][0]);
                    int b = Math.max(intervals[j][1], intervals[i][1]);
                    newIntervals.set(j, new Integer[]{a, b});
                } else
                    newIntervals.add(new Integer[]{intervals[i][0], intervals[i][1]});
            int[][] to_return = new int[newIntervals.size()][2];
            for(i=0;i<to_return.length;i++){
                to_return[i][0] = newIntervals.get(i)[0];
                to_return[i][1] = newIntervals.get(i)[1];
            }
            return to_return;
        }
        for(i=0;i<intervals.length;i++)
            if(newIntervals.get(i)[0]>newInterval[0])
                break;
        
        newIntervals.add(i, new Integer[]{newInterval[0], newInterval[1]});
        
        int[][] to_return = new int[newIntervals.size()][2];
            for(i=0;i<to_return.length;i++){
                to_return[i][0] = newIntervals.get(i)[0];
                to_return[i][1] = newIntervals.get(i)[1];
            }
        return to_return;
    }
    
    public static void main (String[] args) throws java.lang.Exception {
    int[][] intervals = {{0,5}};
    int[] newInterval = {1,6};
    int[][] output = insert(intervals, newInterval);
    for(int i=0;i<intervals.length;i++)
      System.out.print(output[i][0] + " " + output[i][1]);
  }
}
0 6

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N), Учир нь бид жагсаалтыг тойрон гарч, интервалуудыг гаралтын вектор руу оруулсан болно. Тиймээс эдгээр бүх ажиллагаа нь шугаман цаг хугацаа шаарддаг.

мөн үзнэ үү
BST зангилааны хоорондох хамгийн бага зай Leetcode шийдэл

Сансрын нарийн төвөгтэй байдал

O (N), Учир нь бид N эсвэл N + 1 элементүүдийг хадгалдаг векторуудын шинэ векторыг бүтээсэн. Сансрын нарийн төвөгтэй байдал нь мөн шугаман шинжтэй байдаг.