thảo luận Leetcode mỗi ngày

[SPOILER="C++: Max heap]
C++: 
class Solution {
public:
    struct Comp{
        bool operator()(const vector<int>& v1, const vector<int>& v2){
            return v1[0]*1.0 / v1[1] < v2[0]*1.0 / v2[1];
        }
    };
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        priority_queue<vector<int>, vector<vector<int>>, Comp> q;
      
        int n = arr.size();
        for(int i = 0; i < n -1; ++i){
            for(int j = i +1; j < n; ++j){
                q.push({arr[i], arr[j]});
                if(q.size() > k)
                    q.pop();
            }
        }
        return q.top();
      
    }
};
[/SPOILER]
 
Vẫn chưa hiểu cách O(nlogn). Để đây mai mốt coi lại :whistle:
C#: 
public class Solution
{
    public int[] KthSmallestPrimeFraction(int[] arr, int k)
    {
        int n = arr.Length;
        double left = 0, right = 1;
        int[] result = new int[2];

        while (right - left > 1e-9)
        {
            double mid = (left + right) / 2;
            int count = 0;
            double maxFraction = 0;

            for (int i = 0, j = 1; i < n - 1; i++)
            {
                while (j < n && mid * arr[j] < arr[i])
                {
                    j++;
                }
                
                if (j == n)
                {
                    break;
                }

                count += n - j;
                double fraction = (double)arr[i] / arr[j];
                if (fraction > maxFraction)
                {
                    maxFraction = fraction;
                    result[0] = arr[i];
                    result[1] = arr[j];
                }
            }

            if (count == k)
            {
                break;
            }
            if (count < k)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }

        return result;
    }
}
 
C#: 
public class Solution {
    public int[] KthSmallestPrimeFraction(int[] arr, int k) {
        int[] answer = new int[2];
        PriorityQueue<(int, int), double> pq = new PriorityQueue<(int, int), double>();
        for(int i = 0; i<arr.Length-1; i++)
        {
            for(int j = i+1; j<arr.Length; j++)
            {
                pq.Enqueue((arr[i], arr[j]), (double)(arr[i])/arr[j]);
            }
        }
        while(k>0)
        {
            var temp = pq.Dequeue();
            answer[0] = temp.Item1;
            answer[1] = temp.Item2;
            k--;
        }
        return answer;
    }
}
 
Bài hôm nay dùng cách merge giống của merge sort kết hợp với min heap.
C++: 
class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        auto comp = [&arr] (auto a, auto b) {
            auto [a_i, a_j] = a;
            auto a_i_val = arr[a_i];
            auto a_j_val = arr[a_j];
           
            auto [b_i, b_j] = b;
            auto b_i_val = arr[b_i];
            auto b_j_val = arr[b_j];
           
            return a_i_val*b_j_val > b_i_val*a_j_val;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> q(comp);
        for (auto i = 0; i < arr.size() - 1; ++i) {
            q.emplace(i, arr.size() - 1);
        }
       
        for (; k > 1; --k) {
            auto [i, j] = q.top();
            q.pop();
            if (j-1 > i) q.emplace(i, j-1);
        }
        auto [i, j] = q.top();
        return {arr[i], arr[j]};
    }
};
 
seastar said:
Bài hôm nay dùng cách merge giống của merge sort kết hợp với min heap.
C++: 
class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        auto comp = [&arr] (auto a, auto b) {
            auto [a_i, a_j] = a;
            auto a_i_val = arr[a_i];
            auto a_j_val = arr[a_j];
          
            auto [b_i, b_j] = b;
            auto b_i_val = arr[b_i];
            auto b_j_val = arr[b_j];
          
            return a_i_val*b_j_val > b_i_val*a_j_val;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> q(comp);
        for (auto i = 0; i < arr.size() - 1; ++i) {
            q.emplace(i, arr.size() - 1);
        }
      
        for (; k > 1; --k) {
            auto [i, j] = q.top();
            q.pop();
            if (j-1 > i) q.emplace(i, j-1);
        }
        auto [i, j] = q.top();
        return {arr[i], arr[j]};
    }
};
Click to expand...
Không khổ dâm python 1 dòng nữa à fen :smile:
 
Dùng map, tối ưu sau
Java: 
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        TreeMap<Double, int[]> map = new TreeMap<>();

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                map.put((double) arr[i] / (double) arr[j], new int[]{arr[i], arr[j]});
            }
        }


        for (Double key : map.keySet()) {
            k--;
            if (k == 0) return map.get(key);
        }

        return new int[]{};
    }
 
seastar said:
Bài hôm nay dùng cách merge giống của merge sort kết hợp với min heap.
C++: 
class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        auto comp = [&arr] (auto a, auto b) {
            auto [a_i, a_j] = a;
            auto a_i_val = arr[a_i];
            auto a_j_val = arr[a_j];
          
            auto [b_i, b_j] = b;
            auto b_i_val = arr[b_i];
            auto b_j_val = arr[b_j];
          
            return a_i_val*b_j_val > b_i_val*a_j_val;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> q(comp);
        for (auto i = 0; i < arr.size() - 1; ++i) {
            q.emplace(i, arr.size() - 1);
        }
      
        for (; k > 1; --k) {
            auto [i, j] = q.top();
            q.pop();
            if (j-1 > i) q.emplace(i, j-1);
        }
        auto [i, j] = q.top();
        return {arr[i], arr[j]};
    }
};
Click to expand...
bth bác giải là bác skip mấy cách brute force tập trung tìm mấy cách ngắn hơn luôn hay sao
Mk6CABe.png
đi pvan mà brute force chắc same same với không biết giải nhỉ
hO88fV9.png
 
C++: 
class Solution {
public:
  vector<int> kthSmallestPrimeFraction(vector<int> &arr, int k) {
    int i, j;
    vector<pair<double, pair<int, int>>> valueMap;
    sort(arr.begin(), arr.end());
    for (i = 0; i < arr.size() - 1; i++) {
      for (j = i + 1; j < arr.size(); j++) {
        double fraction = (double)arr[i] / arr[j];
        valueMap.push_back({fraction, {arr[i], arr[j]}});
      }
    }
    sort(valueMap.begin(), valueMap.end());
    return {valueMap[k - 1].second.first, valueMap[k - 1].second.second};
  }
};
 
LmaoSuVuong said:
bth bác giải là bác skip mấy cách brute force tập trung tìm mấy cách ngắn hơn luôn hay sao
Mk6CABe.png
đi pvan mà brute force chắc same same với không biết giải nhỉ
hO88fV9.png
Click to expand...
Người ta đọc phần ràng buộc trước nhé fen. Ràng buộc yếu mà O(n^2) vẫn đảm bảo thì cứ brute force mà làm. Thi contest cũng vậy.
Còn đi phỏng vấn nó bảo cần tối ưu thì tối ưu.
 
RTX3090 said:
Không khổ dâm python 1 dòng nữa à fen :smile:
Click to expand...
Python: 
return sorted([[arr[i],arr[j]] for i in range(len(arr)) for j in range(i+1, len(arr))], key = lambda x: x[0]/x[1])[k-1]
đừng thách nhà giàu húp nước tương nhé, :ah:

LmaoSuVuong said:
bth bác giải là bác skip mấy cách brute force tập trung tìm mấy cách ngắn hơn luôn hay sao
Mk6CABe.png
đi pvan mà brute force chắc same same với không biết giải nhỉ
hO88fV9.png
Click to expand...
tùy bài, nhưng bài này t thấy n = 1000. Nếu list hết toàn bộ phân tử ra để sort hay dùng heap thì sẽ n*n*long(n*n). Nhẩm đến đó nên t nghĩ chắc có cách k cần list hết toàn bộ ra. Từ đó nghĩ tiếp thôi.
 
  • Think of fractions of the same numerator together as a sorted array. There are n - 1 such arrays.
  • Use n-way merge to "sort" the arrays above until we get the k-th smallest fraction.

Code: 
use std::cmp;
use std::cmp::Ordering;
use std::cmp::Reverse;
use std::collections::BinaryHeap;

#[derive(Debug)]
struct Fraction {
    dividend: i32,
    divisor: i32,
    dividend_index: usize,
    divisor_index: usize,
}

impl PartialEq<Fraction> for Fraction {
    fn eq(&self, other: &Fraction) -> bool {
        (self.dividend * other.divisor).eq(&(other.dividend * self.divisor))
    }
}

impl Eq for Fraction {}

impl PartialOrd for Fraction {
    fn partial_cmp(&self, other: &Fraction) -> Option<Ordering> {
        Some((self.dividend * other.divisor).cmp(&(other.dividend * self.divisor)))
    }
}

impl Ord for Fraction {
    fn cmp(&self, other: &Fraction) -> Ordering {
        (self.dividend * other.divisor).cmp(&(other.dividend * self.divisor))
    }
}

impl Solution {
    pub fn kth_smallest_prime_fraction(arr: Vec<i32>, k: i32) -> Vec<i32> {
        let n = arr.len();

        let mut heap = BinaryHeap::with_capacity(n);

        for i in 0..(n - 1) {
            let fraction = Fraction {
                dividend: arr[i],
                divisor: arr[n - 1],
                dividend_index: i,
                divisor_index: n - 1
            };

            heap.push(Reverse(fraction));
        }

        let mut kth_smallest: Option<Reverse<Fraction>> = None;

        for j in 0..k {
            kth_smallest = heap.pop();

            kth_smallest = kth_smallest.map(|Reverse(fraction)| {
                if (fraction.dividend_index + 1 < fraction.divisor_index) {
                    let next_fraction = Fraction {
                        dividend: fraction.dividend,
                        divisor: arr[fraction.divisor_index - 1],
                        dividend_index: fraction.dividend_index,
                        divisor_index: fraction.divisor_index - 1
                    };

                    heap.push(Reverse(next_fraction));
                }

                Reverse(fraction)
            });
        }

        kth_smallest.map(|Reverse(fraction)| vec![fraction.dividend, fraction.divisor]).unwrap_or(vec![0, 0])
    }
}
 
seastar said:
Python: 
return sorted([[arr[i],arr[j]] for i in range(len(arr)) for j in range(i+1, len(arr))], key = lambda x: x[0]/x[1])[k-1]
đừng thách nhà giàu húp nước tương nhé, :ah:


tùy bài, nhưng bài này t thấy n = 1000. Nếu list hết toàn bộ phân tử ra để sort hay dùng heap thì sẽ n*n*long(n*n). Nhẩm đến đó nên t nghĩ chắc có cách k cần list hết toàn bộ ra. Từ đó nghĩ tiếp thôi.
Click to expand...
bài này giải cách sinh hết fraction ra được, chỉ cần dùng quickselect thay vì sort fraction thôi

edit: gen hết ra rồi quick select nhanh hơn xài heap, 3ms vs. 87ms, không rõ tại sao :confused:

Screenshot 2024-05-10 115504.png
 
Last edited:
JavaScript: 
function kthSmallestPrimeFraction(arr: number[], k: number): number[] {
    let factions = [];

    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            factions.push([arr[i], arr[j]]);
        }
    }

    factions.sort((a: number[], b: number) => Number(a[0]/a[1]) - Number(b[0]/b[1]));

    return factions[k - 1]
};
 
Chịu, nghĩ không ra cách nào tối ưu, duyệt trâu vậy :shame:
C-like: 
class Solution {
    fun kthSmallestPrimeFraction(arr: IntArray, k: Int): IntArray {
        val fractions = Array<IntArray>(arr.size * (arr.size - 1) / 2) {
            intArrayOf(1, 1)
        }
        var fractionIndex = 0
        for (i in 1 until arr.size) {
            for (j in 0 until i) {
                val fraction = fractions[fractionIndex++]
                fraction[0] = arr[j]
                fraction[1] = arr[i]
            }
        }
        fractions.sortBy { it.first().toDouble() / it.last() }
        return fractions[k - 1]
    }
}
 
LmaoSuVuong said:
bth bác giải là bác skip mấy cách brute force tập trung tìm mấy cách ngắn hơn luôn hay sao
Mk6CABe.png
đi pvan mà brute force chắc same same với không biết giải nhỉ
hO88fV9.png
Click to expand...
Estimate dựa theo input size thôi, chỗ constraint ấy
1715322792218-png.2485624


Xem thêm
www.hackerearth.com

Time and Space Complexity Tutorials & Notes | Basic Programming | HackerEarth

Detailed tutorial on Time and Space Complexity to improve your understanding of Basic Programming. Also try practice problems to test & improve your skill level.
www.hackerearth.com www.hackerearth.com
 

Attachments

  • 1715322792218.png
    1715322792218.png
    365.2 KB · Views: 22
abcdegh said:
JavaScript: 
function kthSmallestPrimeFraction(arr: number[], k: number): number[] {
    let factions = [];

    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            factions.push([arr[i], arr[j]]);
        }
    }

    factions.sort((a: number[], b: number) => Number(a[0]/a[1]) - Number(b[0]/b[1]));

    return factions[k - 1]
};
Click to expand...
Sort trên array size n^2 thì complexity là O(n^2 log(n^2)) chứ không phải O(n^2)
 
- Generate all fractions, then use quick select to find the k-th smallest fraction. Average time complexity is O(n^2)

Code: 
use std::cmp::Ordering;

#[derive(Debug)]
struct Fraction {
    dividend: i32,
    divisor: i32
}

impl PartialEq<Fraction> for Fraction {
    fn eq(&self, other: &Fraction) -> bool {
        (self.dividend * other.divisor).eq(&(other.dividend * self.divisor))
    }
}

impl Eq for Fraction {}

impl PartialOrd for Fraction {
    fn partial_cmp(&self, other: &Fraction) -> Option<Ordering> {
        Some((self.dividend * other.divisor).cmp(&(other.dividend * self.divisor)))
    }
}

impl Ord for Fraction {
    fn cmp(&self, other: &Fraction) -> Ordering {
        (self.dividend * other.divisor).cmp(&(other.dividend * self.divisor))
    }
}

impl Solution {
    pub fn kth_smallest_prime_fraction(arr: Vec<i32>, k: i32) -> Vec<i32> {
        let n = arr.len();
        let frac_len = (n * (n - 1)) / 2;

        let mut fractions = Vec::<Fraction>::with_capacity(frac_len);

        for i in 0..(n - 1) {
            for j in (i + 1)..n {
                fractions.push(Fraction {
                    dividend: arr[i],
                    divisor: arr[j]
                });
            }
        }

        let (_, median, _) = fractions.select_nth_unstable((k - 1) as usize);

        vec![median.dividend, median.divisor]
    }
}
 
Java: 
class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        List<int[]> fractions= new ArrayList();
        for(int i =0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                fractions.add(new int[]{arr[i],arr[j]});
            }
        }
        fractions.sort(Comparator.comparingDouble(a->(double)a[0]/a[1]));
        return fractions.get(k-1);
    }
}
 

Similar threads

Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
612
heocon0123
heocon0123
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
151
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
16
Views
416
truonggiang!
T
@_shin
kiến thức PIXELVERSE kèo hot - inbox tele để lấy extension chạy auto đánh boss
Replies
0
Views
125
@_shin
@_shin
D
kiến thức Lộ trình tự học phát triển Website Fullstack - Fullstack Web Development
2
Replies
25
Views
2K
Kieft
Kieft

Share this page

Back
Top