未排序的陣列，為每個元素找到下一個更大的元素，否則列印-1

要求有點復雜，假設我們有一個未排序的陣列，例如：{12, 72, 93, 0, 24, 56, 102}

如果我們有一個奇數位置，我們必須在他的右邊尋找下一個更大的元素，假設我們取 v[1] = 12，'12' 的 nge 是 24；

但是如果我們有一個偶數位置，我們必須在他的左邊尋找下一個更大的元素，假設我們取 v[2] = 72，沒有比 '72' 大的數，所以我們將列印 '- 1'; 再舉個例子，v[4] = 0，'0'的nge是12；

輸出應為：24 -1 102 12 56 72 -1

我試圖用 C 解決這個問題：

#include <iostream>
using namespace std;

int main() {
    const int CONST = 10000;
    int n, v[CONST];
    cin >> n;
    for (int i = 1; i <= n; i  ) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i  ) {
        int next = -1;
        if (i % 2 != 0) {   
            for (int j = i   1; j <= n; j  ) {
                if (v[j] > v[i]) {
                    next = v[j];
                    break;
                }
            }
            cout << next << " ";
        }
        else {                
            for (int k = 1; k <= i - 1; k  ) {
                if (v[k] > v[i]) {
                    next = v[k];
                    break;
                }
            }
            cout << next << " ";
        }
    }
    return 0;
}

首先，我認為我必須對陣列進行排序，然后使用二分搜索來查找下一個更大的元素

uj5u.com熱心網友回復：

對于初學者而不是陣列，宣告型別的物件要好得多std::vector<int>。

注意 C 中的索引從0.

在這個 if 陳述句中

            if (v[j] > v[i]) {
                next = v[j];
                break;
            }

一旦找到大于當前的第一個元素，您就退出回圈。很明顯，這種做法是錯誤的。

我可以建議以下解決方案。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    size_t n = 0;

    std::cin >> n;

    v.resize( n );

    for (auto &item : v)
    {
        std::cin >> item;
    }

    for (size_t i = 0, n = v.size(); i < n; i  )
    {
        size_t next = i;

        if (i % 2 == 0)
        {
            for (size_t j = i   1; j != n;   j)
            {
                if (v[i] < v[j] && ( next == i || v[j] < v[next] ))
                {
                    next = j;
                }
            }
        }
        else
        {
            for (size_t j = i; j-- != 0; )
            {
                if (v[i] < v[j] && ( next == i || v[j] < v[next] ))
                {
                    next = j;
                }
            }
         }

         std::cout << ( next != i ? v[next] : -1 ) << ' ';
    }
}

程式輸出可能看起來像

7
12 72 93 0 24 56 102
24 -1 102 12 56 72 -1

uj5u.com熱心網友回復：

如果您正在尋找簡單但效率不高的東西（例如 O(n) 空間復雜度 - 向量復制 - 和 O(nlogn) 時間復雜度 - 排序加搜索 - 而不是 O(n) 用于線性搜索），這是一個選項：

• next_greater檢查pos是偶數還是奇數，創建幾個迭代器firstand last，并next_greater使用這些迭代器和要比較的值呼叫模板化, n。
• a 模板對next_greater[ first, last) 進行排序，然后使用 upper_bound 回傳大于 的第一個元素n。

[演示]

#include <algorithm>  // upper_bound
#include <iostream>  // cout
#include <utility>  // pair
#include <vector>

template <typename InputIt, typename T>
T next_greater(InputIt first, InputIt last, T n)
{
    std::sort(first, last);
    auto it{ std::upper_bound(first, last, n) };
    if (it == last) { return -1; }
    return *it;
}

int next_greater(std::vector<int> v, size_t pos)
{
    using it = std::vector<int>::iterator;
    using pair_it = std::pair<it, it>;

    auto [first, last] { (pos % 2 == 1)
        ? pair_it{ std::begin(v), std::begin(v)   pos }  // [begin, pos)
        : pair_it{ std::begin(v)   pos   1, std::end(v) }  // [pos   1, end)
    };
    return next_greater(first, last, v[pos]);  
}

int main()
{
    const std::vector<int> v{12, 72, 93, 0, 24, 56, 102};
    std::cout << "Next greater for i(n):\n";
    for (size_t i{0}; i < v.size();   i)
    {
        std::cout << "\t" << i << "(" << v[i] << "): " << next_greater(v, i) << "\n";
    }
}

// Outputs:
//
//   Next greater for i(n):
//      0(12): 24
//      1(72): -1
//      2(93): 102
//      3(0): 12
//      4(24): 56
//      5(56): 72
//      6(102): -1

標籤：C 算法 for循环 向量 最大限度

上一篇：將資訊從txt檔案匯入類

下一篇：如何在Python的for回圈中與前一個變數互動？