ກວດເບິ່ງວ່າ N ແລະມັນມີ Leetcode Solution ທີ່ມີຢູ່ສອງເທົ່າ


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

ບັນຫາບັນຫາ

ໃນບັນຫາ” ກວດເບິ່ງວ່າ N ແລະມັນມີສອງເທົ່າຢູ່ແລ້ວ” ພວກເຮົາໄດ້ຮັບຫລາຍອົງປະກອບ n. ຄວາມຍາວຂອງແຖວແມ່ນໃຫຍ່ກວ່າຫຼືເທົ່າກັບສອງ.

ວຽກງານຂອງພວກເຮົາແມ່ນເພື່ອກວດກາເບິ່ງວ່າມີຄູ່ຢູ່ໃນແຖວດັ່ງກ່າວວ່າຄ່າ ທຳ ອິດຈະມີມູນຄ່າສອງເທົ່າຫລືບໍ່.

ຢ່າງເປັນທາງການພວກເຮົາ ຈຳ ເປັນຕ້ອງກວດເບິ່ງວ່າມີ i, j ສຳ ລັບ i

ຍົກຕົວຢ່າງ

arr = [7,1,14,11]
true

ຄໍາອະທິບາຍ:

ກວດເບິ່ງວ່າ N ແລະມັນມີ Leetcode Solution ທີ່ມີຢູ່ສອງເທົ່າ

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

ວິທີການ ສຳ ລັບການກວດສອບຖ້າ N ແລະວິທີແກ້ໄຂ Leetcode ແບບຄູ່ຂອງມັນ

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

ພວກເຮົາສາມາດແກ້ໄຂບັນຫານີ້ໄດ້ດ້ວຍຄວາມສັບສົນໃນເວລາທີ່ດີກວ່າໂດຍ ນຳ ໃຊ້ແຜນທີ່ທີ່ບໍ່ມີຂອບເຂດຫລືຊຸດທີ່ບໍ່ມີຂອບເຂດ.

  1. ຂ້າມອາເລ.
  2. ສຳ ລັບທຸກໆອົງປະກອບທີ່ຢູ່ໃນແຖວກວດເບິ່ງວ່າມັນມີສອງເທົ່າຫລືເຄິ່ງ ໜຶ່ງ ແລ້ວມັນມີຢູ່ໃນແຜນທີ່.
  3. ຖ້າສະພາບຄວາມເປັນຈິງພຽງແຕ່ສົ່ງກັບຄວາມຈິງອີກສິ່ງ ໜຶ່ງ ເພີ່ມເຂົ້າໃນແຜນທີ່.
  4. ຖ້າ traversal array ຖືກເຮັດແລ້ວແລະພວກເຮົາບໍ່ພົບວ່າມີສອງອົງປະກອບໃດ, ຫຼັງຈາກນັ້ນໃຫ້ສົ່ງຄືນ false.

ການປະຕິບັດ

ລະຫັດ C ++ ສຳ ລັບກວດເບິ່ງວ່າ N ແລະມັນມີຢູ່ສອງເທົ່າ

#include <bits/stdc++.h> 
using namespace std; 
    bool checkIfExist(vector<int>& arr) {
      unordered_map<int,bool>mp;
        for(int i=0;i<arr.size();i++)
        {
            if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
                return true;
            mp[arr[i]]=1;
        }
        return false;
    }
int main() 
{ 
 vector<int> arr = {7,1,14,11}; 
 bool ans=checkIfExist(arr);
 cout <<boolalpha;
 cout<<ans<<endl;
 return 0;
}
true

ລະຫັດ Java ສຳ ລັບ Check ຖ້າ N ແລະມັນມີຢູ່ສອງເທົ່າ

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();   
        for (int i : arr) {
            if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
                return true;
            seen.add(i);
        }
        return false;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,14,11}; 
        boolean ans=checkIfExist(arr); 
        System.out.println(ans);
  }
}
true

ການວິເຄາະຄວາມສັບສົນຂອງການກວດສອບຖ້າ N ແລະມັນມີ Leetcode Solution ທີ່ມີຢູ່ສອງເທົ່າ

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

ຄວາມສັບສົນຂອງເວລາຂອງລະຫັດຂ້າງເທິງແມ່ນ O (n) ພິຈາລະນາຄວາມສັບສົນຂອງເວລາໂດຍສະເລ່ຍໃນການຄົ້ນຫາແລະໃສ່ໃນແຜນທີ່ທີ່ບໍ່ມີຂອບເຂດເປັນ O (1).

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

ຄວາມສັບສົນໃນພື້ນທີ່ຂອງລະຫັດຂ້າງເທິງແມ່ນ O (n) ເພາະວ່າໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດພວກເຮົາອາດຈະຕ້ອງເກັບຮັກສາອົງປະກອບທັງ ໝົດ ໄວ້.

ເອກະສານ