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

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        s = 0
        for i in range(k):
            s += max(happiness[i] - i, 0)
        return s

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        sorted_happiness = sorted(happiness, reverse=True)
        result = 0
        for i in range(k):
            temp = sorted_happiness[i] - i
            result += temp if temp > 0 else 0
        return result

  public long MaximumHappinessSum(int[] happiness, int k) {
        Array.Sort(happiness);
        long sum = 0;
        int end = happiness.Length - 1;
        for(int i =0;i< k; i++){
            if(happiness[end - i] - i <= 0) break;           
            sum = sum + (happiness[end - i] - i);
        }
        return sum;
    }

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        Arrays.sort(happiness);
        int N = happiness.length, i=0;
        long maxSumOfHappiness = 0;
        while(i < k)
            maxSumOfHappiness += Math.max(happiness[N-i-1] - i++, 0);
        return maxSumOfHappiness;
    }
}

// Time: O(nlogn), space: O(1)
public long maximumHappinessSum(int[] happiness, int k) {
    int n = happiness.length;
    long sum = 0;
    int count = 0;
    Arrays.sort(happiness);
    for (int i = n - 1; i >= n - k; i--) {
        sum += Math.max(happiness[i] - count, 0);
        count++;
    }

    return sum;
}

def maximum_happiness_sum(happiness, k)
  sorted_happiness = happiness.sort.reverse
  sorted_happiness.first(k).each_with_index.sum { |value, index| [value - index, 0].max }
end

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        vector<tuple<float, int, int>> v;
        for(int i=0;i<arr.size()-1;i++){
            for(int j=i+1;j<arr.size();j++){
                v.push_back(make_tuple((float)arr[i]/(float)arr[j],arr[i], arr[j]));
            }
        }
        sort(v.begin(), v.end());
        return {get<1>(v[k-1]),get<2>(v[k-1])};
    }
};

public int[] kthSmallestPrimeFraction(int[] arr, int k) {
    TreeMap<Double, int[]> minHeap = new TreeMap<>();
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            minHeap.put((double) arr[i] / arr[j], new int[]{arr[i], arr[j]});
        }
    }
    while (k > 1) {
        minHeap.pollFirstEntry();
        k--;
    }
    return minHeap.firstEntry().getValue();
}

  struct cmp {
    bool operator()( pair<int, int> a, pair<int, int> b){
       return double(a.first)/a.second > double(b.first)/b.second;
    }
  };

  vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
      int n = arr.size();
      priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> q;
      for(int i = 0; i < n; ++i) {
          for(int j = i + 1; j < n; ++j) {
              q.push({arr[i], arr[j]});
          }
      }
      while(--k) q.pop();
      auto r = q.top();
      return {r.first, r.second};
  }

  vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
      int n = arr.size();
      priority_queue<pair<double, pair<int, int>>> q;
      for(int i = 0; i < n; ++i) {
          for(int j = i + 1; j < n; ++j) {
              double d = -1* double(arr[i])/arr[j];
              q.push({d, {arr[i], arr[j]}});
          }
      }
      while(--k) q.pop();
      auto r = q.top().second;
      return {r.first, r.second};
  }

var kthSmallestPrimeFraction = function(arr, k) {
    let fractions = [];
    
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            fractions.push([arr[i]/arr[j], arr[i], arr[j]]);
        }
    }

    fractions.sort((a, b) => a[0] - b[0]);

    return [fractions[k-1][1], fractions[k-1][2]];
};

function kthSmallestPrimeFraction(arr: number[], k: number): number[] {
    const pq = new MinPriorityQueue();
    const j = arr.length - 1;
    
    for (let i = 0; i < j; i++) {
        pq.enqueue([i, j], arr[i] / arr[j]);
    }

    for (let i = 0; i < k - 1; i++) {
        const [f,s] = pq.dequeue()!.element;
        pq.enqueue([f, s - 1], arr[f] / arr[s - 1]);
    }

    const [f,s] = pq.dequeue()!.element;
    return [arr[f], arr[s]];
}

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int[] res = new int[2];
        double minK = 0;
        List<int[]> lists = new ArrayList<>();
        PriorityQueue<Double> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                double result = arr[i] / (double) arr[j];
                priorityQueue.offer(result);
                lists.add(new int[] { arr[i], arr[j] });
            }
        }
        while (k > 0) {
            minK = priorityQueue.poll();
            k--;
        }
        for (int[] a : lists) {
            if (minK == (a[0] / (double) a[1])) {
                res = a;
            }
        }
        return res;
    }
}