ຈໍານວນຂອງຄູ່ທີ່ດີ Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Microsoft
Array ແຮກ ຄະນິດສາດ

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້ມີການໃຫ້ເລກເຕັມຂອງຕົວເລກແລະພວກເຮົາຕ້ອງຊອກຫາ ຈຳ ນວນຂອງຄູ່ທີ່ດີ (a [i], a [j]) ທີ່ a [i] = a [j].

ຍົກຕົວຢ່າງ

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

ຄຳ ອະທິບາຍ: ມີ 4 ຄູ່ທີ່ດີຢູ່ທີ່ດັດສະນີ (0,3), (0,4), (3,4), (2,5).

[1,1,1,1]
6

ຄຳ ອະທິບາຍ: ແຕ່ລະຄູ່ໃນແຖວແມ່ນດີ.

ວິທີການ (ກຳ ລັງແຮງງານ)

ໃນບັນຫາທີ່ກ່າວມານັ້ນພວກເຮົາສາມາດໃຊ້ສອງ loop, ໜຶ່ງ ສຳ ລັບ [i] ແລະສອງ ສຳ ລັບ [j] ຂອງຄູ່. ໃນ​ນີ້ loop ຮັງ ພວກເຮົາຈະແກ້ໄຂການປະສົມປະສານທີ່ເປັນໄປໄດ້ ສຳ ລັບຄູ່ (a [i], a [j]) ແລະກວດເບິ່ງວ່າ a [i] ເທົ່າກັບ [j] ຫຼືບໍ່.

ສູດການຄິດໄລ່:

1. ສ້າງຕົວແປນັບແລະເລີ່ມຕົ້ນດ້ວຍເລກສູນ.
2. ດໍາເນີນການ loop ຮັງ, loop ນອກສໍາລັບ [i] ຈາກ i = 0 ເຖິງ i = n-1 ແລະ loop ພາຍໃນ ສຳ ລັບ [j] ຈາກ j = i + 1 ເຖິງ j = n-1.
3. ຖ້າ a [i] = a [j], ເພີ່ມຄູ່ປັດຈຸບັນໃຫ້ນັບໂດຍເພີ່ມມູນຄ່າຂອງມັນລົງ 1.
4. ສົ່ງມູນຄ່າຂອງຕົວແປນັບ.

ການປະຕິບັດສໍາລັບຈໍານວນຂອງຄູ່ທີ່ດີ Leetcode Solution

ໂຄງການ C ++

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

int numIdenticalPairs(vector<int>& nums) 
{
       int res = 0;
       for(int i=0;i<nums.size();i++)
           for(int j=i+1;j<nums.size();j++)
               if(nums[i]==nums[j]) res++;
               
       return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Java Program

import java.lang.*;

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        for(int i=0;i<nums.length;i++)
          for(int j=i+1;j<nums.length;j++)
             if(nums[i]==nums[j])   res++;

        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ ຈຳ ນວນຄູ່ທີ່ດີຂອງ Leetcode Solution

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

O (N ^ 2): ບ່ອນທີ່ N ແມ່ນຂະ ໜາດ ຂອງອາເລທີ່ໃຫ້. ໃນຂະນະທີ່ພວກເຮົາ ກຳ ລັງໃຊ້ສອງ loops ແລະກວດສອບການປະສົມອົງປະກອບທັງ ໝົດ ທີ່ index i ແລະ j, ຄວາມສັບສົນເວລາຈະເປັນ O (N ^ 2).

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

O (1): ພວກເຮົາ ກຳ ລັງບໍ່ໃຊ້ຄວາມ ຈຳ ພິເສດໃດໆ.

 

ວິທີການ (ດີທີ່ສຸດ)

ພວກເຮົາສາມາດເພີ່ມປະສິດທິພາບການແກ້ໄຂໂດຍໃຊ້ ແຜນທີ່ Hash. ມັນບໍ່ມີການໃຊ້ເລື່ອຍໃດໃນໄລຍະການປະສົມພັນຂອງຄູ່ i * j ເທື່ອ. ພວກເຮົາຕ້ອງນັບພຽງແຕ່ອົງປະກອບເທົ່າທຽມກັນ.
ie ຖ້າພວກເຮົາມີ ຈຳ ນວນຂອງສ່ວນປະກອບໃດ ໜຶ່ງ ໃນຂອດພວກເຮົາສາມາດຄິດໄລ່ ຈຳ ນວນວິທີການທັງ ໝົດ ໃນການເລືອກເອົາສອງອົງປະກອບໃດ ໜຶ່ງ ໃນຊຸດຂອງອົງປະກອບທີ່ຄ້າຍຄືກັນນີ້
ສຳ ລັບສິ່ງທີ່ພວກເຮົາສາມາດເຮັດໄດ້ນີ້, ພວກເຮົາສາມາດປັບປ່ຽນຈາກອົງປະກອບທີ 1 ແລະປັບປຸງການນັບຂອງແຕ່ລະອົງປະກອບໃນແຕ່ລະບາດກ້າວ.
ເມື່ອໃດກໍ່ຕາມທີ່ພວກເຮົາພົບເຫັນອົງປະກອບໃດ ໜຶ່ງ ພວກເຮົາຈະກວດເບິ່ງວ່າມີອົງປະກອບຄ້າຍຄືກັນຫຼາຍປານໃດທີ່ມີຢູ່ແລ້ວກ່ອນອົງປະກອບນີ້ໂດຍໃຊ້ຕົວແປແຜນທີ່ນັບ. ເພື່ອໃຫ້ມັນສາມາດສ້າງຄູ່ກັບທຸກໆອົງປະກອບທີ່ເກີດຂື້ນກ່ອນ ໜ້າ ນີ້.
ພວກເຮົາຈະເພີ່ມ ຈຳ ນວນນັ້ນເຂົ້າໃນຜົນຂອງພວກເຮົາແລະການປັບປຸງ (ເພີ່ມຂື້ນ) ຈຳ ນວນປັດໃຈປັດຈຸບັນໂດຍ +1.

ຈໍານວນຂອງຄູ່ທີ່ດີ Leetcode Solution

ສູດການຄິດໄລ່:
1. ສ້າງແຜນທີ່ຂອງຕົວເລກແລະຕົວເຊື່ອມໂຍງເຊິ່ງຫຼັກຂອງມັນແມ່ນອົງປະກອບແລະຄຸນຄ່າແມ່ນນັບປັດຈຸບັນຂອງອົງປະກອບນັ້ນ.
2. ດຳ ເນີນການ loop ສຳ ລັບແຕ່ລະອົງປະກອບ i = 0 ເຖິງ n-1.
3. ຊອກຫາການນັບ (a [i]) ກ່ອນທີ່ຈະເອົາໃສ່ແຜນທີ່ແລະເພີ່ມມູນຄ່ານີ້ເຂົ້າໃນ res.
4. ດຽວນີ້ອັບເດດນັບຂອງ a [i] ເປັນນັບ (a [i]) = ນັບ (a [i]) + 1.
5. ສົ່ງຄືນຄ່າຂອງ res.

ການປະຕິບັດສໍາລັບຈໍານວນຂອງຄູ່ທີ່ດີ Leetcode Solution

ໂຄງການ C ++

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

int numIdenticalPairs(vector<int>& nums) 
{
    int res = 0;
    unordered_map<int, int> count;
    for (int a: nums) 
    {
        res += count[a]++;
    }
  
    return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Java Program

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

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        Map<Integer,Integer> count= new HashMap<Integer,Integer>();
        for (int a: nums)
        {
            int cur=count.getOrDefault(a,0);
            res += cur;
            count.put(a,cur+1);
        }
        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ ຈຳ ນວນຄູ່ທີ່ດີຂອງ Leetcode Solution

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

O (N): ໃນຂະນະທີ່ພວກເຮົາ ກຳ ລັງເຮັດວຽກຢູ່ເລື້ອຍໆໃນການປັບປຸງການນັບ ຈຳ ນວນຂອງແຕ່ລະອົງປະກອບໂດຍ ນຳ ໃຊ້ແຜນທີ່ Hash, ດັ່ງນັ້ນຄວາມສັບສົນເວລາຈຶ່ງຈະເປັນ O (N).

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

ໂອ (N) : ພວກເຮົາ ກຳ ລັງໃຊ້ແຜນທີ່ Hash ເພື່ອເກັບຄ່ານັບຂອງແຕ່ລະອົງປະກອບທີ່ເປັນເອກະລັກ. ມັນສາມາດມີອົງປະກອບທີ່ແຕກຕ່າງກັນ N ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ.