ສາມາດສ້າງຄວາມກ້າວ ໜ້າ ກ່ຽວກັບເລກຄະນິດສາດຈາກການແກ້ໄຂບັນຫາ Leetcode


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

ບັນຫາບັນຫາ

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

ຍົກຕົວຢ່າງ

arr = [3,1,5]
true

ຄໍາອະທິບາຍ: ພວກເຮົາສາມາດຈັດລຽງ ລຳ ດັບເປັນ {1,3,5} ເຊິ່ງເປັນຮູບແບບຄວາມຄືບ ໜ້າ ເລກຄະນິດສາດເຊິ່ງມີຄວາມແຕກຕ່າງຄືກັນກັບ 2, ດັ່ງນັ້ນຜົນໄດ້ຮັບກໍ່ແມ່ນຄວາມຈິງ.

ວິທີການ ສຳ ລັບສາມາດເຮັດໃຫ້ມີຄວາມຄືບ ໜ້າ ກ່ຽວກັບເລກຄະນິດສາດຈາກການແກ້ໄຂບັນຫາ Leetcode

ຊຸດເລກຄະນິດສາດແມ່ນຊຸດທີ່ຄວາມແຕກຕ່າງລະຫວ່າງ ຈຳ ນວນທີ່ຢູ່ຕິດກັນແມ່ນຄົງທີ່. ວິທີການພື້ນຖານທີ່ສຸດແມ່ນການຈັດຮຽງແຖວແລະກວດເບິ່ງຄວາມແຕກຕ່າງກັນລະຫວ່າງອົງປະກອບທີ່ຢູ່ຕິດກັນ, ຖ້າຄວາມແຕກຕ່າງຄືກັນກັບທຸກໆຄູ່ທີ່ຕິດຕໍ່ກັນແລ້ວມັນກໍ່ແມ່ນຄວາມຄືບ ໜ້າ ເລກຄະນິດສາດຖ້າບໍ່ດັ່ງນັ້ນມັນບໍ່ແມ່ນຄວາມຄືບ ໜ້າ ເລກຄະນິດສາດ.

ສາມາດສ້າງຄວາມກ້າວ ໜ້າ ກ່ຽວກັບເລກຄະນິດສາດຈາກການແກ້ໄຂບັນຫາ Leetcode

ຄວາມສັບສົນຂອງເວລາ ສຳ ລັບການຈັດຮຽງແມ່ນບໍ່ຮູ້ຕົວ. ພວກເຮົາສາມາດປັບປຸງຄວາມສັບສົນຂອງເວລາໂດຍການສ້າງຕາຕະລາງຊອກຫາ ສຳ ລັບອາເລ.

ໄລຍະເວລາຂອງ AP ແມ່ນ = a + (n-1) * d, ບ່ອນທີ່ a ແມ່ນອົງປະກອບ ທຳ ອິດຂອງຊຸດ, n ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບແລະ d ແມ່ນຄວາມແຕກຕ່າງທົ່ວໄປ.

ອົງປະກອບຕ່ ຳ ສຸດຂອງ AP ແມ່ນ = a ແລະ

ອົງປະກອບສູງສຸດຂອງ AP ແມ່ນ = a + (n-1) * d ດັ່ງນັ້ນ

d = (ສູງສຸດ - ຕ່ ຳ ສຸດ) / (n-1).

  1. ພວກເຮົາຈະຊອກຫາອົງປະກອບຕ່ ຳ ແລະສູງສຸດຂອງອາເລ. ໃຊ້ມັນພວກເຮົາສາມາດຄິດໄລ່ d (ຄວາມແຕກຕ່າງທົ່ວໄປ).
  2. ສ້າງຕາຕະລາງຊອກຫາ ສຳ ລັບອາເລ.
  3. ຕອນນີ້ພວກເຮົາຮູ້ຈັກອົງປະກອບ ທຳ ອິດແລະຄວາມແຕກຕ່າງທົ່ວໄປ.
  4. ພວກເຮົາຈະກວດເບິ່ງວ່າທຸກໆອົງປະກອບ n ຂອງເລກຄະນິດສາດທີ່ຖືກສ້າງຕັ້ງຂື້ນໂດຍ a ແລະ d ມີຢູ່ໃນຕາຕະລາງຊອກຫາບໍ.
  5. ຖ້າຫາກວ່າອົງປະກອບທັງ ໝົດ ມີຢູ່ໃນຕາຕະລາງຊອກຫາຫຼັງຈາກນັ້ນພວກເຮົາສາມາດສ້າງຄວາມກ້າວ ໜ້າ ກ່ຽວກັບເລກເລກຈາກ ລຳ ດັບອື່ນທີ່ພວກເຮົາບໍ່ສາມາດສ້າງຄວາມກ້າວ ໜ້າ ກ່ຽວກັບເລກເລກຈາກ ລຳ ດັບ.

ການປະຕິບັດ

ລະຫັດ C ++ ສຳ ລັບສາມາດເຮັດໃຫ້ຄວາມກ້າວ ໜ້າ ດ້ານເລກຄະນິດສາດຈາກ ລຳ ດັບ

#include <bits/stdc++.h> 
using namespace std; 
  bool canMakeArithmeticProgression(vector<int>& arr) {
  unordered_set<int> seen;
  int mi = INT_MAX, mx = INT_MIN, n = arr.size();
        for (int a : arr) {
            mi = min(mi, a);
            mx = max(mx, a);
            seen.insert(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (seen.find(mi)==seen.end()) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
int main() 
{ 
 vector<int> arr = {3,5,1}; 
 cout <<boolalpha;   
 cout<<canMakeArithmeticProgression(arr)<<endl; 
 return 0;
}
true

ລະຫັດ Java ສຳ ລັບສາມາດສ້າງຄວາມກ້າວ ໜ້າ ດ້ານເລກຄະນິດສາດຈາກ ລຳ ດັບ

import java.util.*; 
public class Tutorialcup {
 public static boolean canMakeArithmeticProgression(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE, n = arr.length;
        for (int a : arr) {
            mi = Math.min(mi, a);
            mx = Math.max(mx, a);
            seen.add(a);
        }
        int diff = mx - mi;
        if (diff % (n - 1) != 0) {
            return false;
        }
        diff /= n - 1;
        while (--n > 0) {
            if (!seen.contains(mi)) {
                return false;
            }
            mi += diff;
        }
        return true;
    }
  public static void main(String[] args) {
    int [] arr = {3,5,1}; 
    System.out.println( canMakeArithmeticProgression(arr));
  }
}
true

ການວິເຄາະທີ່ສັບສົນຂອງສາມາດເຮັດໃຫ້ມີຄວາມຄືບຫນ້າກ່ຽວກັບເລກຄະນິດສາດຈາກການແກ້ໄຂບັນຫາ Leetcode

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

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

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

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

ເອກະສານ