c++ 排序0、1和2的数组[重复]

brqmpdu1  于 2024-01-09  发布在  其他
关注(0)|答案(3)|浏览(114)

此问题在此处已有答案

Accessing an array out of bounds gives no error, why?(18个答案)
8天前关闭
我的代码中有什么错误,为什么它没有给出正确的输出?
输入

  1. 84
  2. 1 0 1 2 1 1 0 0 1 2 1 2 1 2 1 0 0 1 1 2 2 0 0 2 2 2 1 1 1 2 0 0 0 2 0 1 1 1 1 0 0 0 2 2 1 2 2 2 0 2 1 1 2 2 0 2 2 1 1 0 0 2 0 2 2 1 0 1 2 0 0 0 0 2 0 2 2 0 2 1 0 0 2 2

字符串
它的正确输出是:

  1. 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2


Your Code的输出是:

  1. 0-36092119132636100007056629140-858993460214748364-...
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. void sortArray(int *arr,int n){
  5. int low=0,mid=1,high=n-1;
  6. while(mid<=high){
  7. if(arr[mid]==1){
  8. mid++;
  9. }
  10. else if(arr[mid]==2){
  11. swap(arr[mid],arr[high]);
  12. high--;
  13. }
  14. else{
  15. swap(arr[mid],arr[low]);
  16. mid++,low++;
  17. }
  18. }
  19. for(int i=0;i<n;i++){
  20. cout<<arr[i];
  21. }
  22. }
  23. int main()
  24. {
  25. int t;
  26. cin>>t;
  27. while(t--){
  28. int n;
  29. cin>>n;
  30. int arr[n];
  31. for(int i=0;i<n;i++){
  32. cin>>arr[n];
  33. }
  34. sortArray(arr,n);
  35. }
  36. return 0;
  37. }

的字符串

nwlqm0z1

nwlqm0z11#

主要问题在于你的输入阅读:

  1. for(int i=0;i<n;i++) {
  2. cin>>arr[n];
  3. }

字符串
您正在阅读arr[n],即undefined。您希望使用i作为索引:

  1. for(int i=0;i<n;i++) {
  2. cin>>arr[i];
  3. }


由于数组将只包含0、1或2,因此也可以简化排序算法:

  1. void sortArray(int *arr, size_t n)
  2. {
  3. size_t count[3] = {0};
  4. for (size_t i = 0; i < n; ++i) {
  5. count[arr[i]]++;
  6. }
  7. size_t k = 0;
  8. for (size_t i = 0; i < 3; ++i) {
  9. for (size_t j = 0; j < count[i]; ++j)
  10. arr[k++] = i;
  11. }
  12. for (size_t i = 0; i < n; ++i)
  13. std::cout << arr[i] << ' ';
  14. std::cout << endl;
  15. }


注意:你正在使用一个非标准的扩展。C++标准没有VLA(variable length arrays)。
可变长度数组通常在“堆栈”上分配,并且容易发生堆栈溢出。如果数组的长度太大,则会出现未定义的行为。更糟糕的是,您也无法轻松知道数组的“正确”大小。因此,最好避免使用VLA。您可以使用std::vector<int>

展开查看全部
v09wglhw

v09wglhw2#

你应该尝试一种更好的方法(教科书方法),即计算0,1和2出现的次数,然后按升序分配它们,或者请解释你在代码中使用的方法。

  1. void sort012(int a[], int n)
  2. {
  3. int count[3]={};
  4. for(int i=0;i<n;i++){
  5. count[a[i]]++;
  6. }
  7. int j=0;
  8. for(int i=0;i<3;i++){
  9. int temp=count[i];
  10. while(temp--){
  11. a[j]=i;
  12. j++;
  13. }
  14. }
  15. }

字符串
就时间和空间复杂度而言,这是一种简单有效的方法

展开查看全部
mzsu5hc0

mzsu5hc03#

这段代码不会在012210这样的测试用例中执行,因为如果你保持mid=1,那么它就不会比较index=1处的1,它会离开那个,输出将变成010122.([右],[1])但低是在0索引,然后中只是简单地移动,所以错过了从高索引1的值更新,所以使中=0我们的代码将纠正这种情况,这种优化的代码将适用于所有测试用例

  1. #Optimal Approach
  2. #Dutch National Flag Approach
  3. def sort012(arr, n) :
  4. low,mid,right=0,0,n-1 #making mid=0 to compare all possibilities
  5. while mid<=right:
  6. if arr[mid]==0:
  7. arr[low],arr[mid]=arr[mid],arr[low]
  8. low+=1
  9. mid+=1
  10. elif arr[mid]==1:
  11. mid+=1
  12. else:
  13. arr[mid],arr[right]=arr[right],arr[mid]
  14. right-=1
  15. return arr
  16. #Time complexity:O(N)
  17. #Space Complexity:O(1)

字符串

展开查看全部

相关问题