ການແກ້ໄຂບັນຫາ Leetcode ທີ່ມີຄວາມແຕກຕ່າງ ໜ້ອຍ ທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Audible Bloomberg SAP Uber
Array

ບັນຫາຄວາມແຕກຕ່າງຢ່າງ ໜ້ອຍ ຢ່າງສິ້ນສຸດ Leetcode Solution ໃຫ້ພວກເຮົາເປັນ ບໍ່ຖືກຈັດ array ຫຼື vector ມີເລກເຕັມບາງສ່ວນ. ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາທຸກຄູ່ທີ່ມີຄວາມແຕກຕ່າງເທົ່າກັບຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດ. ຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕ່ ຳ ສຸດແມ່ນມູນຄ່າ ຕຳ ່ສຸດຂອງຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງທີ່ສາມາດບັນລຸໄດ້ໂດຍການເລືອກເອົາສອງອົງປະກອບທີ່ແຕກຕ່າງກັນໃນ ຈຳ ນວນທັງ ໝົດ ທີ່ເປັນໄປໄດ້ຈາກ vector ຫຼື array. ສະນັ້ນ, ໂດຍບໍ່ຕ້ອງ ດຳ ນ້ ຳ ເລິກເຂົ້າໃນວິທີແກ້ໄຂກ່ອນອື່ນ ໝົດ ໃຫ້ທ່ານພິຈາລະນາບາງຕົວຢ່າງ.

arr = [4,2,1,3]
[[1,2],[2,3],[3,4]]

ການແກ້ໄຂບັນຫາ Leetcode ທີ່ມີຄວາມແຕກຕ່າງ ໜ້ອຍ ທີ່ສຸດ

ຄຳ ອະທິບາຍ: ຍ້ອນວ່າມີພຽງແຕ່ສາມຄູ່ເທົ່ານັ້ນທີ່ມີຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງ ໜ້ອຍ ທີ່ສຸດ. ພວກເຮົາສົ່ງພວກເຂົາຄືນເປັນ ຄຳ ຕອບຂອງບັນຫາ. ທັງສາມຂອງມັນມີຄວາມແຕກຕ່າງກັນຄືກັນຂອງ 1. ຄວາມແຕກຕ່າງຂອງ 1 ແມ່ນຄວາມແຕກຕ່າງທີ່ ໜ້ອຍ ທີ່ສຸດ.

arr = [1,3,6,10,15]
[[1,3]]

ຄໍາອະທິບາຍ: ນັບຕັ້ງແຕ່ຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດເທົ່າກັບ 2, ແລະສາມາດບັນລຸໄດ້ໂດຍຄູ່ຄູ່ດຽວເທົ່ານັ້ນ. ຄູ່ຄູ່ນີ້ຈະຖືກສົ່ງຄືນເປັນ ຄຳ ຕອບ.

ວິທີການແກ້ໄຂບັນຫາ Leetcode ທີ່ມີຄວາມແຕກຕ່າງ ໜ້ອຍ ທີ່ສຸດ

ບັນຫາທີ່ມີຄວາມແຕກຕ່າງຢ່າງ ໜ້ອຍ ສຸດຄວາມແຕກຕ່າງ Leetcode, ຂໍໃຫ້ພວກເຮົາຊອກຫາທຸກໆຄູ່ຂອງຕົວເລກທີ່ມີຄວາມແຕກຕ່າງລະຫວ່າງພວກມັນເທົ່າກັບຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດ. ພວກເຮົາໄດ້ກ່າວມາແລ້ວວ່າແມ່ນຫຍັງຄືຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດ. ສະນັ້ນ, ແທນທີ່ຈະເບິ່ງທີ່ເຮົາຄວນສຸມໃສ່ວິທີການແກ້ໄຂບັນຫາ. ດັ່ງນັ້ນ, ກ່ອນອື່ນ ໝົດ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຂັ້ນຕ່ ຳ ສຸດ. ຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕໍ່າສຸດສາມາດພົບເຫັນໄດ້ພຽງແຕ່ລະຫວ່າງອົງປະກອບທີ່ຢູ່ຕິດກັນເມື່ອຈັດລຽງຕາມແບບທີ່ມີການຈັດລຽງ. ບັນຫາດັ່ງກ່າວໄດ້ສະ ໜອງ ອາເລຫລືວໍເປເປີທີ່ບໍ່ຖືກຈັດລຽງໃຫ້ພວກເຮົາ. ດັ່ງນັ້ນ, ທຳ ອິດ, ພວກເຮົາຈັດຮຽງແຖວ. ຈາກນັ້ນໃຫ້ຕິດຕາມຄວາມແຕກຕ່າງທີ່ຢູ່ໃກ້ຄຽງແລະປັບປຸງ ຄຳ ຕອບທຸກຄັ້ງທີ່ພວກເຮົາພົບເຫັນຄວາມແຕກຕ່າງທີ່ນ້ອຍກວ່າ.

ພວກເຮົາຍັງສ້າງຊຸດທີ່ບໍ່ມີຂອບເຂດຫລືຮ hash ທີ່ເກັບຄ່າເລກເຕັມຈາກ vector. ກົ້ມພວກເຮົາພຽງແຕ່ຂ້າມຜ່ານອາເລແລະພະຍາຍາມຊອກຫາຕົວເລກທີ່ມີຄວາມແຕກຕ່າງເທົ່າກັບຄວາມແຕກຕ່າງຢ່າງແທ້ຈິງຕ່ ຳ ສຸດທີ່ໄດ້ຮັບ, ເຊິ່ງອົງປະກອບປັດຈຸບັນແມ່ນໃຫຍ່ກວ່າທັງສອງ. ຖ້າພວກເຮົາພົບເຫັນອົງປະກອບດັ່ງກ່າວໃນຊຸດຂອງພວກເຮົາ, ພວກເຮົາເພີ່ມຄູ່ໃນ ຄຳ ຕອບ. ແຕ່ຖ້າພວກເຮົາບໍ່ເຮັດ, ພວກເຮົາພຽງແຕ່ກ້າວໄປ ໜ້າ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບວິທີແກ້ໄຂທີ່ແຕກຕ່າງຢ່າງ ໜ້ອຍ Leetcode

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

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    int mnDiff = INT_MAX, n = arr.size();
    unordered_set<int> h;
    for(int i=0;i<n-1;i++){
        mnDiff = min(mnDiff, arr[i+1] - arr[i]);
        h.insert(arr[i]);
    }
    h.insert(arr[n-1]);

    vector<vector<int>> l;
    for(int i=0;i<n;i++){
        if(h.count(arr[i]-mnDiff)){
            l.push_back({arr[i]-mnDiff, arr[i]});
        }
    }
    return l;
}

int main(){
    vector<int> sequence = {4, 3, 1, 2};
    vector<vector<int>> output = minimumAbsDifference(sequence);
    for(auto x: output){
        cout<<x[0]<<" "<<x[1]<<endl;
    }
}
1 2
2 3
3 4

ລະຫັດ Java ສຳ ລັບວິທີແກ້ໄຂທີ່ແຕກຕ່າງກັນຢ່າງ ໜ້ອຍ Leetcode

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

class Main
{
  public static List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int mnDiff = Integer.MAX_VALUE, n = arr.length;
        HashSet<Integer> h = new HashSet<Integer>();
        for(int i=0;i<n-1;i++){
            mnDiff = Math.min(mnDiff, arr[i+1] - arr[i]);
            h.add(arr[i]);
        }
        h.add(arr[n-1]);
        
        List<List<Integer>> l = new ArrayList<List<Integer>>();
        for(int i=0;i<n;i++){
            if(h.contains(arr[i]-mnDiff)){
                l.add(new ArrayList<Integer>(Arrays.asList(arr[i]-mnDiff, arr[i])));
            }
        }
        return l;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {4, 3, 1, 2};
    List<List<Integer>> output = minimumAbsDifference(arr);
    for(List<Integer> x: output){
      System.out.println(x);
    }
  }
}
[1, 2]
[2, 3]
[3, 4]

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ນັບຕັ້ງແຕ່ພວກເຮົາຂ້າມແຖວທີ່ໄດ້ຮັບ, ແລະໄດ້ນໍາໃຊ້ຊຸດ hash ທີ່ໄດ້ຫຼຸດຜ່ອນຄວາມສັບສົນເວລາ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາເກັບຮັກສາອົງປະກອບຂອງອາເລໃນຊຸດ hash. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.