在C 中確定陣列中的重復項/對

我已經做這個問題2天了，我仍然無法弄清楚如何正確地做到這一點。

在這個程式中，我必須輸入可用的棒數（比如說 5）。然后，將要求用戶輸入每根棍子的長度（空格分隔的整數）。假設每根棍子的長度分別為 [4, 4, 3, 3, 4]。現在，我必須確定是否有對（2 根相同長度的棍子）。在這種情況下，我們有 2（4,4 和 3,3）。由于有 2 對，我們可以創建一個畫布（一個畫布總共有 2 對棒作為框架）。現在，我不知道如何確定陣列中有多少“對”。我想尋求您的幫助和指導。請注意，我是初學者。我可能不了解復雜的程序。所以，如果有一個簡單的（或初學者可以理解的）方法來做到這一點，那就太好了。只是我不 不想在我的代碼中加入一些我不完全理解的東西。謝謝！

此處附上問題本身的鏈接。 https://codeforces.com/problemset/problem/127/B

這是我的代碼（沒有確定對數的程序）

#include<iostream>
#include<cmath>
#define MAX 100

int lookForPairs(int numberOfSticks);

int main(void){
    int numberOfSticks = 0, maxNumOfFrames = 0;

    std::cin >> numberOfSticks;
    maxNumOfFrames = lookForPairs(numberOfSticks);
    std::cout << maxNumOfFrames << std::endl;
    return 0;
}

int lookForPairs(int numberOfSticks){
    int lengths[MAX], pairs = 0, count = 0, canvas = 0;

    for(int i=0; i<numberOfSticks; i  ){
        std::cin >> lengths[i];
    }
    pairs = floor(count/2);
    canvas = floor(pairs/2);
    return count;
}

我試著這樣做，但它有缺陷。當有 3 個或更多相同數字的整數時（例如 [4, 4, 3, 4, 2] 或 [5. 5. 5. 5. 6]），它將不起作用。在第一個陣列上，當它應該只有 3 時，計數將是 6，因為只有三個 4。

 for(int i=0; i<numberOfSticks; i  ){
        for (int j=0; j<numberOfSticks; j  ){
            if (lengths[i] == lengths[j] && i!=j)
            count  ;
        }
    }

uj5u.com熱心網友回復：

不要存盤所有長度然后比較它們，而是直接計算每個長度有多少。

這些值已知為正數，最多為 100，因此您也可以int[100]為此使用陣列：

int counts[MAX] = {}; // Initialize array to all zeros.

for(int i = 0; i < numberOfSticks; i  ) {
    int length = 0;
    std::cin >> length;
    counts[length-1]  = 1; // Adjust for zero-based indexing.
}

然后數一數：

int pairs = 0;
for(int i = 0; i < MAX; i  ) {
    pairs  = counts[i] / 2;
}

然后你就有了答案：

return pairs;

uj5u.com熱心網友回復：

只是對molbdnilo答案的擴展：您甚至可以在一次迭代中計算所有對：

for(int i = 0; i < numberOfSticks;   i)
{
    if(std::cin >> length) // catch invalid input!
    {
        pairs  = flags[length] == 1; // add a pair if there is already a stick
        flags[length] ^= 1;          // toggle between 0 and 1...
    }
    else
    {
        // some appropriate error handling
    }
}

請注意，我跳過了從長度中減去 1 的步驟——這要求陣列的長度更大（但現在它可以是可用的最小型別，即char），而索引 0 僅用作未使用的標記。這個變體甚至允許使用位圖來存盤標志，盡管如果最大長度那么小，那么所有這些位擺弄是否值得......

uj5u.com熱心網友回復：

您可以使用地圖計算出現次數。似乎不允許您使用標準地圖。由于棍子的大小限制為 100，根據您提供的鏈接，您可以使用包含m101 個專案的陣列（棍子的最小大小為 1，最大大小為 100）。元素索引是棒的大小。元素值是棒的數量。也就是說，m[a[i]]是大小為 的棒數a[i]。演示。

#define MAX 100

int n = 7;
int a[MAX] = { 1,2,3,4,1,2,3 };

int m[MAX   1]; // maps stick len to number of sticks

void count()
{
  for (int i = 0; i < n;   i)
    m[a[i]]  ;
}

int main()
{
  count();
  for (int i = 1; i < MAX   1;   i)
    if (m[i])
      std::cout << i << "->" << m[i] << std::endl;
}

uj5u.com熱心網友回復：

您的內部回圈每次都從一開始就向前計數，這使您多算了陣列中的專案。從 向前計數i，而不是零。

    for(int i=0; i<numberOfSticks; i  )
    {
        for (int j=i; j<numberOfSticks; j  ) { // count forward from i (not zero)
            if (lengths[i] == lengths[j] && i!=j) 
            { // enclosing your blocks in curly braces , even if only one line, is easier to read
                count  ; // you'll want to store this value somewhere along with the 'length'. perhaps a map?
            } 
        }
    }

標籤：C

上一篇：在C 中使用串列向量構建紅黑樹

下一篇：在堆上分配然后使用共享指標，如何釋放資料