ຈຳ ນວນດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ GreyOrange ແທ້ຈິງແລ້ວ Opera Pinterest Snapdeal Yahoo
Array ບັນຫາການສອບຖາມ

ເຈົ້າຍັງບໍ່ໄດ້ໃຫ້ integer array, ຖາມແບບສອບຖາມ, ແລະຊ່ວງ ໜຶ່ງ ເປັນຊ້າຍແລະຂວາ. "ຈຳ ນວນດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນຂອບເຂດທີ່ກ່າວໄວ້" ເວົ້າເພື່ອຊອກຫາ ຈຳ ນວນທັງ ໝົດ ຂອງ ຈຳ ນວນຂອງຕົວເລກໃນວິທີທາງທີ່ປະໄວ້ <= i <ຂວາ, ເຊັ່ນວ່າ Ai = ກj + 1.

ຍົກຕົວຢ່າງ

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

ຄໍາອະທິບາຍ

ສຳ ລັບການສອບຖາມ 1, ບ່ອນທີ່ປະໄວ້ = 2, ຂວາ = 6

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

ນັບແມ່ນ 3.

ສຳ ລັບການສອບຖາມຂໍ້ມູນ 2, ບ່ອນທີ່ປະໄວ້ = 4, ຂວາ = 8

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

ນັບແມ່ນ 3.

ຈຳ ນວນດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້

 

ລະບົບວິເຄາະ

  1. ສ້າງຂບວນ.
  2. ຂ້າມຜ່ານຂບວນ.
  3. ຖ້າອົງປະກອບຂບວນປັດຈຸບັນເທົ່າກັບອົງປະກອບຕໍ່ໄປ, ຫຼັງຈາກນັ້ນໃຫ້ ໝາຍ ອົງປະກອບຂອງອາເລທີ່ຖືກສ້າງຂື້ນເທົ່າກັບ 1.
  4. ຖ້າດັດສະນີບໍ່ເທົ່າກັບ 0, ຫຼັງຈາກນັ້ນຈັດເກັບຜົນລວມຂອງ array array ຂອງປັດຈຸບັນ array ແລະ Element array ຕໍ່ໄປເຂົ້າໄປໃນ arrayDummy [i].
  5. ແກ້ໄຂການສອບຖາມ, ຖ້າ ຕຳ ແໜ່ງ ເບື້ອງຊ້າຍເທົ່າກັບ 0, ຫຼັງຈາກນັ້ນສົ່ງ arrayDummy [ຂວາ-1], ອີກອັນ ໜຶ່ງ ຈະສົ່ງຄືນຄວາມແຕກຕ່າງຂອງ arrayDummy [right-1] ແລະ arrayDummy [left-1].

ຄໍາອະທິບາຍ

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

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

ສຳ ລັບ ຄຳ ຖາມທີ່ໃຫ້ໃນແຕ່ລະຖ້າດັດຊະນີເບື້ອງຊ້າຍຂອງລະດັບເທົ່າກັບ 0, ຫຼັງຈາກນັ້ນສົ່ງ arrayDummy [ຂວາ - 1]. ອື່ນຖ້າມັນບໍ່ແມ່ນ 0, ຫຼັງຈາກນັ້ນພຽງແຕ່ສົ່ງຄືນຄວາມແຕກຕ່າງລະຫວ່າງ arrayDummy [ຂວາ - 1] ແລະ arrayDummy [ຊ້າຍ - 1].

ລະຫັດ

ລະຫັດ C ++ ເພື່ອນັບ ຈຳ ນວນດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}
3
3

ລະຫັດ Java ເພື່ອນັບ ຈຳ ນວນດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນຂອບເຂດທີ່ ກຳ ນົດໄວ້

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}
3
3

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

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

 O (1) ສຳ ລັບທຸກໆ ຄຳ ຖາມແລະ O (n) ສຳ ລັບຄອມພີວເຕີ້.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ພື້ນທີ່ນີ້ແມ່ນ ຈຳ ເປັນ ສຳ ລັບການສ້າງ arrayDummy.