2

我对 C++ 很陌生，我需要帮助找出删除随机生成的一组数字的最小值的代码。到目前为止，这是我的代码：

   //Create array and populate the array with scores between 55 and 10
//  Drop lowest Score 

#include <iostream>
#include <cstdlib>//for generating a random number
#include <ctime>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;


//function prototype
int *random (int);


int main()
{   int *numbers; //point to numbers
    //get an array of 20 values
    numbers = random(20);
    //display numbers
    for (int count = 0; count < 20; count++)
        cout << numbers[count] << endl;
    cout << endl;


system("pause");
    return 0;
}

//random function, generates random numbers between 55 and 100 ??

int *random(int num)
{   int *arr; //array to hold numbers
    //return null if zero or negative
    if (num <= 0)
        return NULL;
    //allocate array
    arr = new int[num];
    //seed random number generator
    srand(time (0));
    //populate array
    for (int count = 0; count < num; count++)
        arr[count] = (rand()%(45) +55);
    //return pointer

    //
    return arr;
}

对于这段代码，在函数返回随机数后，我将如何排序或找到最低分数以将其丢弃？

  int main()
    {   int *numbers; //point to numbers
        //get an array of 20 values
        numbers = random(20);
        //display numbers
        for (int count = 0; count < 20; count++)
            cout << numbers[count] << endl;
        cout << endl;


    system("pause");
        return 0;
    }

感谢您的建议！

4

6 回答 6

4

通常，要找到数组中的最小值，您可以遵循以下伪算法：

min = array[0] // first element in array
for (all_values_in_array)
{
    if (current_element < min)
        min = current_element
}

但是，您不能从静态数组中“删除”一个值。您可以考虑使用动态容器（例如向量），或者将最小值与最后一个值交换，并假装数组的大小小于 1。另一个低级选项是在堆上创建自己的动态数组，但是，这可能比您要寻找的要复杂。

使用向量会容易得多。要删除最低的元素，您只需按相反的顺序排序，然后删除最后一个元素。就个人而言，我建议使用向量。

于 2012-11-19T19:58:03.890 回答
2

找到最小元素的明显方法是使用std::min_element(). 你可能想用它std::vector<T>来保存你的元素，但这不是绝对必要的。您可以像这样从数组中删除最小值：

if (count) {
    int* it = std::min_element(array, array + count);
    std::copy(it + 1, array + count--, it);
}

假设您合理使用std::vector<int>，代码将如下所示：

if (!array.empty()) {
    array.erase(std::min_element(array.begin(), array.end()));
}
于 2012-11-19T20:07:50.553 回答
0

对数组进行升序排序。
最小值将位于数组的开头。

或者对数组进行降序排序并删除最后一个元素。

于 2012-11-19T20:39:36.943 回答
0

在我看来，解决您的问题的最佳解决方案是使用链表来存储数字，这样您就可以使用复杂度为O(N) = N的算法来找到列表中的最小元素，它类似于查找user1599559或Mikael Lindqvist给出的方法，您只需将指向存储它的链表中的Item（ ItemX ）的指针与最小值一起存储，然后消除Item X只需告诉Item X - 1指向Item X + 1和项目 X 分配的空闲内存

于 2014-11-09T04:03:41.613 回答
0

除了其他人所说的，您还可以选择使用类似的东西，也许是 std::list。它内置了排序功能，还提供了为两个元素定义自己的比较函数的能力。（虽然对于整数，这不是必需的）

首先，我通常使用它将包含的元素类型来定义向量或列表。接下来，对于列表，我 typedef 一个迭代器——尽管这两个都只是为了方便，但都不是必需的。

一旦你有了一个包含整数的列表，只需将它们添加到其中。习惯和不需要这样做意味着我将使用 .push_back 添加每个新元素。完成后，我将对列表进行排序，获取具有最低值的元素（也是最低的“索引” - 第一项），最后，我将删除该项目。

一些需要思考的代码：

#include <cstdio>
#include <cstdlib>
#include <list>


using namespace std;

typedef list<int> listInt;
typedef listInt::iterator listIntIter;

bool sortAsc(int first, int second)
{
    return first < second;
}

bool sortDesc(int first, int second)
{
    return first > second;
}

int main (void)
{
    listInt mList;
    listIntIter mIter;
    int i, curVal, lowestScore;

    for (i=1; i<=20; i++)
    {
        curVal = rand()%45 + 55;
        mList.push_back(curVal);
        printf("%2d. %d\n", i, curVal);
    }
    printf("\n");

    mList.sort();
//    mList.sort(sortAsc);  // in this example, this has the same effect as the above line.
//    mList.sort(sortDesc);

    i = 0;
    for (mIter=mList.begin(); mIter!=mList.end(); mIter++)
        printf("%2d. %d\n", ++i, *mIter);
    printf("\n");

    lowestScore = mList.front();
    mList.pop_front();
    printf("Lowest score: %d\n", lowestScore);

   return 0;
}

哦，使用 printf 而不是 cout 的选择也是经过深思熟虑的。有几个原因。

  1. printf("%d\n", someVar); 个人喜好——我觉得打字比打字容易cout << someVar << endl;
  2. 大小——windows下用gcc构建的，这个例子的release-mode exe是21kb。使用 cout，它跃升至 459kb - 功能相同！增加 20 倍的尺寸却没有任何收益？不，谢谢！！

这是一个 std::list 参考：http ://www.cplusplus.com/reference/stl/list/

于 2012-11-19T20:51:50.553 回答
0

首先找到最小数字的索引：

int lowest_index=0, i;
for (i=0; i<20; i++)
    if (arr[i]<arr[lowest_index])
        lowest_index=i;

现在我们知道了索引，移动该索引之后的数字以覆盖我们找到的索引。要移动的数字数量将是 19 减去找到的索引。即，如果索引 2（第三个数字，因为第一个在索引 0 处）最低，则在该索引之后有 17 个数字，这就是我们需要移动的数量。

memcpy(&arr[lowest_index],&arr[lowest_index+1],sizeof(int)*(19-lowest_index))

祝你好运！

于 2012-11-19T20:15:17.090 回答