[已解决]寫不出來的題目！！求救

caspar1

這台機器有四顆功能鍵跟數字小鍵盤
功能鈕上分別寫著
1.Insert
2.Query MAX
3.Query MIN
4.Print Sorted Array
旁邊寫著一行粗字: 極值經查詢後將會刪除
題目看到這各位也明瞭了吧
請你寫出這台機器的程式可以插入數字並且查詢其中的最大值與最小值注意：
本題不可使用Max、Min、Sort()函式
輸入說明
每行輸入開頭有四種情形
1: 插入操作，其後會跟著一數字 N 代表插入的數字 (0 ≤ N ≤ 231-1)
2: 查詢最大值
3: 查詢最小值
4: 列印出排序好的陣列
同一時間內最多有 100,000 個數字
輸出說明
每筆查詢輸出一行
每行只有一個數字
範例輸入
1 3
1 100
2
1 4
3
範例輸出
100
3

求助 謝謝各位大佬了

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-5-25 16:29:51

你都已经用 C++ 了，为什么不用 vertor？

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using std::vector;
   
5. vector<int> Ver;
   
6. 
   
7. void sort() {
   
8.         int N = Ver.size();
   
9.         for (int i = 0; i < N - 1; ++i) {
   
10.                 for (int j = i + 1, t; j < N; ++j) {
    
11.                         if (Ver[j] < Ver[i]) {
    
12.                                 t = Ver[i];
    
13.                                 Ver[i] = Ver[j];
    
14.                                 Ver[j] = t;
    
15.                         }
    
16.                 }
    
17.         }
    
18. }
    
19. 
    
20. using std::cout, std::endl;
    
21. int main(void) {
    
22.         int arr[] = { 13, 7, 96, 58, 32 };
    
23.         for (const int &num: arr) {
    
24.                 Ver.push_back(num);
    
25.         }
    
26.        
    
27.         sort();
    
28.        
    
29.         for (const int&num: Ver) {
    
30.                 cout << num << " ";
    
31.         }
    
32.         cout << endl;
    
33.         cout
    
34.                 << "最大值：" << Ver.back() << endl
    
35.                 << "最小值：" << Ver[0] << endl;
    
36. }

复制代码

1. 7 13 32 58 96
   
2. 最大值：96
   
3. 最小值：7

复制代码

跳转到最佳答案楼层

傻眼貓咪

最多有 100,000 個數字? N <= 2^31 - 1?

caspar1

傻眼貓咪 发表于 2022-5-23 20:02
最多有 100,000 個數字? N

應該是總共儲存的數字數量

傻眼貓咪

caspar1 发表于 2022-5-23 20:22
應該是總共儲存的數字數量

题目问题不难，根本就是初学者等级也称不上，难是最大值，这才是重点。
目前我所知道的所有排序法，其最优的最坏时间复杂度也都要 O(n + k)，但你的 n 最大是 100000，k 最大是 2^31-1 = 2147483647，如何排序呢？

caspar1

傻眼貓咪 发表于 2022-5-23 20:32
题目问题不难，根本就是初学者等级也称不上，难是最大值，这才是重点。
目前我所知道的所有排序法，其最 ...

我的想法是使用 linked list 去做 stack ， 在使用 insertion sort 去排序我所放入的數字，假設忽略掉最大值得問題。這樣是可行的嗎

傻眼貓咪

caspar1 发表于 2022-5-23 20:40
我的想法是使用 linked list 去做 stack ， 在使用 insertion sort 去排序我所放入的數字，假設忽略掉最 ...

可以

caspar1

傻眼貓咪 发表于 2022-5-23 20:46
可以

//S10350106 陳柏宇
#include <iostream>
using namespace std;

int ch ,num ,i = 0;
int ary[100000];

void insertionSort()
{
    int temp;
    for(int k = 0;k < i;k++)
    {
        for(int n = 0;n < i-k-1;n++)
        {
            if(ary[n] >= ary[n+1])
            {
                temp = ary[n];
                ary[n] = ary[n+1];
                ary[n+1] = temp;
            }
        }
    }
}

int main()
{
    cout << "Enter 1 : push value to ary" << endl;
    cout << "Enter 2 : search max value" << endl;
    cout << "Enter 3 : search min value" << endl;
    cout << "Enter 4 : display ary" << endl;
    while(1)
    {
        cout << "Enter your choice: " << endl;
        cin >> ch;
        switch(ch)
        {
            case 1:
            {
                cout << "Enter value to ary : " << endl;
                cin >> num;
                ary = num;
                i = i + 1;
                insertionSort();
                break;
            }
            case 2:
            {
                cout << "max value is : " << ary[i-1] << endl;
                break;
            }
            case 3:
            {
                cout << "min value is : " << ary[0] << endl;
                break;
            }
            case 4:
            {
                for(int j = 0;j < i;j++)
                {
                    cout << ary[j] << " " << endl;
                }
                break;
            }
        }
    }
    return 0;
}

最後改成用陣列了，請問要如何達到查詢後刪除極值的效果，我試過很多種方式，但沒辦法刪除，只能將它變成ＮＵＬＬ

傻眼貓咪

你都已经用 C++ 了，为什么不用 vertor？

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using std::vector;
   
5. vector<int> Ver;
   
6. 
   
7. void sort() {
   
8.         int N = Ver.size();
   
9.         for (int i = 0; i < N - 1; ++i) {
   
10.                 for (int j = i + 1, t; j < N; ++j) {
    
11.                         if (Ver[j] < Ver[i]) {
    
12.                                 t = Ver[i];
    
13.                                 Ver[i] = Ver[j];
    
14.                                 Ver[j] = t;
    
15.                         }
    
16.                 }
    
17.         }
    
18. }
    
19. 
    
20. using std::cout, std::endl;
    
21. int main(void) {
    
22.         int arr[] = { 13, 7, 96, 58, 32 };
    
23.         for (const int &num: arr) {
    
24.                 Ver.push_back(num);
    
25.         }
    
26.        
    
27.         sort();
    
28.        
    
29.         for (const int&num: Ver) {
    
30.                 cout << num << " ";
    
31.         }
    
32.         cout << endl;
    
33.         cout
    
34.                 << "最大值：" << Ver.back() << endl
    
35.                 << "最小值：" << Ver[0] << endl;
    
36. }

复制代码

1. 7 13 32 58 96
   
2. 最大值：96
   
3. 最小值：7

复制代码

caspar1

傻眼貓咪 发表于 2022-5-25 16:29
你都已经用 C++ 了，为什么不用 vertor？

小弟還是新手，很多不懂哈哈哈 感謝您！

jhq999

傻眼貓咪 发表于 2022-5-25 16:29
你都已经用 C++ 了，为什么不用 vertor？

借阁下的代码一用

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int ch ,num ,i = 0;
   
5. int ary[100]={0};
   
6. 
   
7. void insertionSort()
   
8. {
   
9.         int temp, k = 0;
   
10.         for(;k < i;k++)if(ary[i-1]<ary[k])break;
    
11. 
    
12.         for(;k < i-1;k++)
    
13.         {
    
14.                 temp=ary[k];
    
15.                 ary[k]=ary[i-1];
    
16.                 ary[i-1]=temp;
    
17.         }
    
18. 
    
19. }
    
20. int main(void) {
    
21.        int a=0;
    
22.            while (scanf("%d",&a))
    
23.            {
    
24.                    ary[i]=a;
    
25.                    i++;
    
26.                    insertionSort();
    
27.            }
    
28.                
    
29.         for (int num: ary) {
    
30.                 cout << num << " ";
    
31.         }
    
32.         cout << endl;
    
33.         cout
    
34.                 << "最大值：" << ary[i-1] << endl
    
35.                 << "最小值：" << ary[0] << endl;
    
36.                 return 0;
    
37. }

复制代码

1. 13 7 96 58 32 a
   
2. 7 13 32 58 96 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   
3. 最大值：96
   
4. 最小值：7

复制代码