Hackerrank - Подсчет троек C ++ неудачный тестовый пример №10 и №11 - PullRequest
Новая
       33

Hackerrank - Подсчет троек C ++ неудачный тестовый пример №10 и №11

0 голосов
/ 04 августа 2020

Ниже представлено решение C ++ для проблемы Count Triplets с веб-сайта Hackerrank. Ссылка на проблему приведена ниже:

Подсчет троек

введите описание изображения здесь 

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    long r;
    cin>>n>>r;
    long arr2[100006];
    for (int i = 0; i < n; i++) {
        long a;
        cin>>a;
        arr2[i]=a;
    }
    long sum = 0;
    unordered_map<double, long> lfreq;
    unordered_map<double, long> rfreq;
    lfreq[arr2[0]]++;
    for(int i=2;i<n;i++){
        rfreq[arr2[i]]++;
    }
    for(int i=1;i<n-1;i++){
        long ans1=0, ans2=0;
        double prev=0;
        if(arr2[i]%r==0) prev= arr2[i]/r;
        double nxt = arr2[i]*r;
        //ans1 = count(arr2,arr2+i,prev);
        //ans2 = count(arr2+i+1,arr2+n,nxt);
        ans1 = lfreq[prev];
        ans2 = rfreq[nxt];
        lfreq[arr2[i]]++;
        if(rfreq[arr2[i]]>0) rfreq[arr2[i]]--;
        //cout<<arr2[i]<<"--->"<<ans1<<"--->"<<ans2<<endl; 
        sum += (ans1*ans2);
    }
    cout<<sum<<"\n";
}

Приведенный выше код не работает для тестового примера №10 и №11. Что не обработано?

Заранее спасибо.

1 Ответ

0 голосов
/ 04 августа 2020

Как насчет этого? 

    /**
     * This method assumes input is valid!
     * @param arr an ascending sorted list of factors of n
     * @param n the factor
     * @return a count of triplets
     */
    public int countTriplets(int[] arr, int n)
    {
        Map<Long, Long> cnt = new HashMap<>();
        Map<Long, Long> tots = new HashMap<>();
        long count = 0;
        for (long a : arr)
        {
            // Do only if a is divisible by r
            if (a % r == 0)
            {
                long n = a / r;
                count += tots.getOrDefault(n, 0L);
                tots.put(a, tots.getOrDefault(a, 0L) + cnt.getOrDefault(n, 0L));
            }

            // Increment count of a.
            cnt.put(a, cnt.getOrDefault(a, 0L) + 1);
        }

        return count;
    }

Это однопроходное решение O (n). Базовая предпосылка такова: элемент может «видеть» количество значений, меньших, чем он сам, и возникших до него. Итак, читая элементы, отслеживайте, сколько элементов можно увидеть в данный момент, а сколько -. Подсчет представляет собой совокупность всех этих чисел.

--- Изменить: изменено после запуска в Hackerrank.

...