ຄວາມ ໝາຍ ຂອງຊ່ວງເປັນແຖວ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Cadence ອິນເດຍ Expedia FreeCharge GreyOrange ຟລີໂຄ້ດ SnapChat Snapdeal ອິນເຕີເນັດ Times Times Yandex
Array ບັນຫາການສອບຖາມ

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

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

ຍົກຕົວຢ່າງ

array[] = {2, 5, 1, 6, 7, 8}

Query: {(1, 4), (0,2), (4,5)}
4 2 7

ຄໍາອະທິບາຍ

(1,4) ສະນັ້ນມູນຄ່າ ໝາຍ ເຖິງ 5,1,6,7 ເຊິ່ງແມ່ນ 4

(0,2) ສະນັ້ນມູນຄ່າ ໝາຍ ເຖິງ 2,5,1 ເຊິ່ງແມ່ນ 2

(4,5) ສະນັ້ນມູນຄ່າ ໝາຍ ເຖິງ 7,8 ເຊິ່ງແມ່ນ 7

ຄວາມ ໝາຍ ຂອງຊ່ວງເປັນແຖວ

 

ລະບົບວິເຄາະ

  1. ສ້າງ Array PreMeanSum ແລະເລີ່ມຕົ້ນຄ່າ ທຳ ອິດຂອງມັນເປັນຄ່າຂອງອາເລທີ່ໃຫ້.
  2. ລອກລວງຂບວນຈາກ 1 ແລະເກັບຮັກສາຜົນລວມຂອງມູນຄ່າກ່ອນ ໜ້າ ຂອງ PreMeanSum ແລະມູນຄ່າປະຈຸບັນຂອງອາເລທີ່ມອບໃຫ້ເປັນມູນຄ່າປະຈຸບັນຂອງຂບວນ PreMeanSum.
  3. ໄດ້ຮັບ ຕຳ ແໜ່ງ ເບື້ອງຊ້າຍແລະຂວາຂອງການສອບຖາມແລະກວດເບິ່ງວ່າ ຕຳ ແໜ່ງ ຊ້າຍແມ່ນ 0, ຖ້າຖືກຕ້ອງແລ້ວຈະສົ່ງຄືນ ຈຳ ນວນຂອງ PreMeanSum [ຂວາ] / ຂວາ + 1.
  4. ອື່ນສົ່ງຄືນຄ່າຂອງ PreMeanSum [ຂວາ] -PreMeanSum [ຊ້າຍ - 1] / ຂວາ - ຊ້າຍ +1.

ຄໍາອະທິບາຍ

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

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

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

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາ Mean of range ໃນຂບວນ

#include<iostream>
#include<math.h>

#define MAX 1000005
using namespace std;

int PreMeanSum[MAX];

void buildPreMean(int arr[], int n)
{
    PreMeanSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
}

int getMeanInRange(int l, int r)
{
    if (l == 0)
        return floor(PreMeanSum[r] / (r + 1));

    return floor( (PreMeanSum[r] - PreMeanSum[l - 1]) / (r - l + 1));
}

int main()
{

    int arr[] = {2,5,1,6,7,8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    buildPreMean(arr, n);
    cout << getMeanInRange(1, 4) << endl;
    cout << getMeanInRange(0, 2) << endl;
    cout << getMeanInRange(4, 5) << endl;
    return 0;
}
4
2
7

ລະຫັດ Java ເພື່ອຊອກຫາ Mean of range ໃນ array

class MeanInRange
{
    public static final int MAX = 1000005;

    static int PreMeanSum[] = new int[MAX];

    static void buildPreMean(int arr[], int n)
    {
        PreMeanSum[0] = arr[0];
        for (int i = 1; i < n; i++)
            PreMeanSum[i] = PreMeanSum[i - 1] + arr[i];
    }

    static int getMeanInRange(int l, int r)
    {
        if (l == 0)
            return (int)Math.floor(PreMeanSum[r] / (r + 1));

        return (int)Math.floor((PreMeanSum[r] -
                                PreMeanSum[l - 1]) / (r - l + 1));
    }

    public static void main(String[] args)
    {
        int arr[] = {2,5,1,6,7,8 };
        int n = arr.length;
        buildPreMean(arr, n);
        System.out.println(getMeanInRange(1, 4));
        System.out.println(getMeanInRange(0, 2));
        System.out.println(getMeanInRange(4, 5));
    }
}
4
2
7

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

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

O (n + q) ບ່ອນທີ່ "Q" ແມ່ນ ຈຳ ນວນຂອງການສອບຖາມທີ່ຕ້ອງປະຕິບັດຕາມທີ່ສາມາດ ຄຳ ນວນໄດ້ O (1) ຄວາມສັບສົນທີ່ໃຊ້ເວລາ. O (n) ຕ້ອງໃຊ້ເວລາເພື່ອປະກາດ PreMeanSum.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.