ຊອກທຸກຕົວເລກທີ່ຫາຍໄປໃນ Array Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ກູໂກ Microsoft Yahoo
Array ແຮກ

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

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

ຍົກຕົວຢ່າງ

Array = {1 , 2 , 5 , 6 , 2 , 5}
3 4

ຊອກທຸກຕົວເລກທີ່ຫາຍໄປໃນ Array Leetcode Solution

Array = {1 , 2 , 3 , 4}
n

ຊອກທຸກຕົວເລກທີ່ຫາຍໄປໃນ Array Leetcode Solution

ວິທີການ (ການໃຊ້ HashSet)

ພວກເຮົາສາມາດ ໝາຍ ເອົາທຸກໆອົງປະກອບໃນແຖວແລະຈາກນັ້ນລິງໃນຂອບເຂດ: [1, N] ເພື່ອກວດເບິ່ງວ່າມີອົງປະກອບໃດທີ່ຫາຍໄປຫຼືຫາຍໄປໃນແຖວ. ພວກເຮົາໃຊ້ຊຸດ hash ເພື່ອເກັບຮັກສາບໍ່ວ່າຈະເປັນເລກເຕັມຖືກ ໝາຍ ໄວ້ຫຼືບໍ່.

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນຊຸດ hash ເຄື່ອງ ໝາຍ [ເລກເຕັມ] ເພື່ອເກັບຮັກສາອົງປະກອບທີ່ມີຢູ່.
  2. ສຳ ລັບທຸກໆອົງປະກອບ i ໃນຂບວນການ:
    • ຕື່ມ i to ເຄື່ອງຫມາຍ
  3. ເລີ່ມຕົ້ນລາຍຊື່ / vector ຜົນ ເພື່ອເກັບຮັກສາອົງປະກອບທີ່ຂາດຫາຍໄປໃນແຖວ
  4. ສຳ ລັບທຸກໆອົງປະກອບ ໃນຂອບເຂດ: [1, N]:
    • If ບໍ່ມີຢູ່ໃນ ເຄື່ອງ ໝາຍ:
      • ຕື່ມໃສ່ມັນ ຜົນ
  5. Return ຜົນ
  6. ພິມຜົນໄດ້ຮັບ

ການຈັດຕັ້ງປະຕິບັດການຊອກຫາຕົວເລກທັງ ໝົດ ຫາຍໄປໃນການແກ້ໄຂ Array Leetcode

ໂຄງການ C ++

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

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

Java Program

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}
3 4

ການວິເຄາະຄວາມສັບສົນຂອງການຊອກຫາຕົວເລກທັງ ໝົດ ຫາຍໄປໃນວິທີການແກ້ໄຂບັນຫາຂອງ Array Leetcode

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

ໂອ (N) ດັ່ງທີ່ພວກເຮົາຂ້າມອາເລທັງ ໝົດ ຄັ້ງ ໜຶ່ງ ເພື່ອ ໝາຍ ເລກທະຫານ. N = ຂະ ໜາດ ຂອງຂບວນ.

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

ໂອ (N) ດັ່ງທີ່ພວກເຮົາເກັບຮັກສາຕົວເລກທັງ ໝົດ ທີ່ມີຢູ່ໃນໂຕະໃນຕາຕະລາງ hash. ໃຫ້ສັງເກດວ່າພວກເຮົາບໍ່ໄດ້ພິຈາລະນາບັນດາຜົນຜະລິດໃນການປະກອບສ່ວນຂອງຄວາມສັບສົນໃນອະວະກາດ.

ວິທີການ (ການດັດແປງສະຖານທີ່)

ຈຸດ ໜຶ່ງ ທີ່ຈະສັງເກດເຫັນໃນບັນຫານີ້ແມ່ນ:“ ແຖວສະເຫມີມີສ່ວນປະກອບ ໜ້ອຍ ກວ່າຫຼືເທົ່າກັບຂະ ໜາດ ຂອງມັນ”. ນີ້ຫມາຍຄວາມວ່າມີຕົວຊີ້ວັດທີ່ມີຫຼາຍອົງປະກອບທີ່ແຕກຕ່າງກັນ. ເຊັ່ນດຽວກັນ, ອົງປະກອບທີ່ຂາດຫາຍໄປຈະມີຫນ້ອຍກ່ວາ N (ຂະ ໜາດ ຂອງຂບວນ). ການ ນຳ ໃຊ້ຂໍ້ ຈຳ ກັດນີ້, ພວກເຮົາສາມາດ ນຳ ໃຊ້ຂບວນການດັ່ງກ່າວໃນຕົວມັນເອງເພື່ອເກັບຮັກສາການມີຕົວຂອງຕົວເລກໃນບາງທາງ ຍົກຕົວຢ່າງ, ສົມມຸດວ່າພວກເຮົາສາມາດຂຽນໄດ້ ຖືກ / ຜິດ ຢູ່ທີ່ດັດສະນີຂອງອົງປະກອບເພື່ອ ໝາຍ ເຖິງການມີ / ການຂາດຂອງມັນຕາມ ລຳ ດັບ. ໃນກໍລະນີຂອງພວກເຮົາ, ອາເລມີອົງປະກອບທີ່ມີຢູ່ແລ້ວ, ສະນັ້ນການເກັບຮັກສາ / ບັນທຶກຄວາມຊົງ ຈຳ ແບບນີ້ເບິ່ງຄືວ່າເປັນໄປບໍ່ໄດ້. ເຖິງຢ່າງໃດກໍ່ຕາມ, ຍ້ອນວ່າພວກເຮົາຮູ້ວ່າທຸກໆອົງປະກອບແມ່ນໃນທາງບວກ, ພວກເຮົາສາມາດໃຊ້ "ລົບ" ເປັນສັນຍານຂອງການປະຕິເສດວ່າພວກເຮົາໄດ້ເຫັນອົງປະກອບໃດ ໜຶ່ງ ຢູ່ໃນແຖວຫຼືບໍ່. ໃຫ້ສັງເກດວ່າພວກເຮົາສາມາດເກັບມູນຄ່າຕົວຈິງທີ່ເກັບໄວ້ໃນບາງດັດສະນີໂດຍການ ນຳ ໃຊ້ ສົມບູນ () ຟັງຊັນທີ່ສົ່ງຄືນຄ່າສຸດທິຂອງຕົວເລກເຕັມ. ດ້ວຍວິທີນີ້, ອາເລສາມາດ ນຳ ໃຊ້ທັງແຜນທີ່ hash ແລະພາຊະນະບັນຈຸ.

ຕົວຢ່າງ: ຖ້າພວກເຮົາໄດ້ເຫັນອົງປະກອບ '2' ໃນອາເລ, ພວກເຮົາສາມາດ ກຳ ນົດ Array [1] = -1 * Array [1] ເຊິ່ງຈະບອກພວກເຮົາວ່າອົງປະກອບ 2 ແມ່ນເຫັນຢູ່ໃນ array.

ເຄັດລັບນີ້ຈະ ໝູນ ໃຊ້ອາຄານໃນບ່ອນເກັບມ້ຽນຖ້າພວກເຮົາໄດ້ເຫັນອົງປະກອບຢູ່ທີ່ດັດສະນີ i. ເມື່ອເຮັດແລ້ວ, ພວກເຮົາສາມາດແລ່ນ loop ໃນຂອບເຂດ [1, N] ເພື່ອຊອກຫາເລກເຕັມທີ່ບໍ່ແມ່ນລົບ (ໝາຍ ຄວາມວ່າບໍ່ໄດ້ເຫັນ) ແລະເພາະສະນັ້ນ, ພິມຜົນທີ່ຕ້ອງການ. ໃຫ້ສັງເກດວ່າສິ່ງນີ້ເປັນໄປໄດ້ຖ້າພວກເຮົາມີ ອະນຸຍາດໃຫ້ ການປ່ຽນແປງຂບວນການ.

ລະບົບວິເຄາະ

  1. ສຳ ລັບທຸກໆອົງປະກອບ ໃນຂບວນການ:
    • ຖ້າ Array [i - 1]> 0:
      • ຕັ້ງຄ່ານີ້ເປັນລົບ, ຫຼື, Array [i - 1] * = -1;
  2. ເລີ່ມຕົ້ນລາຍຊື່ / vector ຜົນ ເພື່ອເກັບຮັກສາອົງປະກອບທີ່ຂາດຫາຍໄປທັງ ໝົດ
  3. ສຳ ລັບທຸກໆເລກເຕັມ ໃນຂອບເຂດ [1, N] (N = ຂະ ໜາດ ຂອງຂບວນ):
    • If ອາເລ [i]> 0
      • ເພີ່ມສ່ວນປະກອບນີ້ i to ຜົນ
  4. Return ຜົນ
  5. ພິມຜົນໄດ້ຮັບ

ການຈັດຕັ້ງປະຕິບັດການຊອກຫາຕົວເລກທັງ ໝົດ ຫາຍໄປໃນການແກ້ໄຂ Array Leetcode

ໂຄງການ C ++

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

vector <int> findDisappearedNumbers(vector <int> &a)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

Java Program

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

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

ການວິເຄາະຄວາມສັບສົນຂອງການຊອກຫາຕົວເລກທັງ ໝົດ ຫາຍໄປໃນວິທີການແກ້ໄຂບັນຫາຂອງ Array Leetcode

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

ໂອ (N) ດັ່ງທີ່ພວກເຮົາດໍາເນີນການສອງເສັ້ນຜ່ານຂອງຂບວນໂດຍບໍ່ຄໍານຶງເຖິງວັດສະດຸປ້ອນເພື່ອຊອກຫາອົງປະກອບທີ່ຂາດຫາຍໄປ. N = ຂະ ໜາດ ຂອງຂບວນ.

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

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຄົງທີ່.