Вернуть массив, который содержит количество элементов в массиве, которое меньше или равно элементам в данном массиве

Question

Я сталкивался с этой проблемой и задавался вопросом, может ли быть лучшая сложность, чтобы решить проблему.

Например,

• массив a = [1,4,2,4]
• массив b = [3,5]

ЖЕЛАЕМЫЙ ВЫХОД ==> [2, 4]

РЕДАКТИРОВАТЬ: поставить другой пример

• массив a = [1,4,2,4]
• массив b = [3, 1000000]

желаемый выход ==> [2,4]

Пока что то, что я нашел и попробовал, работает в O (nlogn) + O (blogn) и O (n).

O (nlogn) + O (blogn) подход:

 int binarysearch(vector<int>arr, int l, int r, int target) 
 {
      int mid;
      while(l <= r)
      {
          mid = (r+l) / 2;

          if(arr[mid] > target)
              r = mid - 1;
          else
              l = mid + 1;
      }

      return r; 
 }

vector<int> counts(vector<int> a, vector<int> b)
{
    vector<int> result;
    sort(a.begin(), a.end()); // O(nlogn)

    for(auto i : b){
        int count = binarysearch(a, 0, a.size()-1, b); // b*O(log n) times
        result.push_back(count)
    }
    return result;
}

O (n) подход:

vector<int> counts(vector<int> a, vector<int> b)
{
    vector<int> result;
    int maxi = *max_element(b.begin(), b.end()) + 1;
    int mymap[maxi] = {0};

    for(auto i : a) mymap[i]++;

    for(int i = 1; i < maxi; i++){
        mymap[i] = mymap[i] + mymap[i-1];
    }

    for(auto i : b){
        result.push_back(mymap[i]);
    }
    return result;
}

Answer 1

Нет лучшего способа сделать это, чем O(n).

Так что это тоже O(n), но с адаптированным стилем STL:

template <class Iter1, class Iter2>
std::vector<std::size_t> counts(const Iter1 beg_a, const Iter1 end_a, const Iter2 beg_b, const Iter2 end_b)
{
    std::vector<std::size_t> result;
    const auto& max = *std::max_element(beg_b, end_b);
    std::vector<std::size_t> mymap(max + 1, 0);
    for (auto iter = beg_a; iter != end_a; iter++)
    {
        if (*iter <= max)
        {
            mymap[*iter]++;
        }
    }
    for (std::size_t i = 1; i < mymap.size(); i++)
    {
        mymap[i] = mymap[i] + mymap[i - 1];
    }
    for (auto iter = beg_b; iter != end_b; iter++)
    {
        result.push_back(mymap[*iter]);
    }
    return result;
}

Answer 2

[Мне] интересно, может ли быть лучшая сложность для решения проблемы.

Сложность времени.

O (n) подход:

Нет, не существует решения с меньшей линейной временной сложностью.

Тем не менее, ваше линейное решение неверно.Если входной массив содержит значение 1000000 или больше или отрицательное число, то вы получаете доступ за пределами mymap и поведение не определено.Кроме того, i <= 1000000 также получает доступ к mymap за пределами границы на последней итерации.Кроме того, int[1000000] слишком велик, чтобы быть локальной переменной.В некоторых системах даже одна такая переменная может вызвать переполнение стека.

Answer 3

Сначала давайте возьмем лучшие обозначения: давайте назовем A количеством элементов в a, B количеством элементов в B и скажем, что элементы являются значениями M битов.Ваше решение, как другие говорили, A log(A) для построения карты плюс B log(A) для получения возвращаемых значений.

Используя https://en.wikipedia.org/wiki/Y-fast_trie, вы можете получить (A+B) log M вместо этого, что быстрееесли A >> M (но, вероятно, медленнее на практике для большинства случаев использования).

Answer 4

Хорошо, оказывается, есть более быстрый способ вычисления индекса карты. Например, дано a = {1,4,2,4,5,8,80} и b = {3,1000000}. желаемый результат будет [2,7].

Используя мой предыдущий подход, мне нужно вычислить mymap [4], mymap [5] .. mymap [9999] .... mymap [1000000]. И именно поэтому программа вылетает и возвращает ошибку времени выполнения.

способ, которым мы обрабатываем это, должен использовать для (auto & entry: mymap), который дает доступ ко всему словарю / карте. Затем мы используем STL C ++ upper_bound для возврата правильной карты.

    vector<int> counts(vector<int> nums, vector<int> maxes){


    vector<int> result;

    map<int,unsigned int> mymap;
    for(auto i : nums) mymap[i]++;

    // doesn't need to run 1000000 times
    int temp = 0;
    for(auto& entry: mymap){
        entry.second = entry.second + temp;
        temp = entry.second;
        //cout << "first : " << entry.first << "second: " << entry.second << endl;
    }

    map<int,unsigned int>::iterator itl;
    for(auto i : maxes){
        itl = --mymap.upper_bound(i); // points to the correct map
        result.push_back(itl->second);
    }

    return result;
 }

Answer 5

Надеюсь, это поможет вам.

    private List<Integer> compareAndCount (@NotNull List<Integer> integerListA, @NotNull List<Integer> integerListB){
    List<Integer> countedIntList = new ArrayList<>();
    int counter;

    for (int B : integerListB ){
        counter = 0;
        for (int A : integerListA){
            if(A < B){
                counter++;
            }
        }
        countedIntList.add(counter);
    }
    return countedIntList;
}