fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve(vector<int> &nums) {
  5. 	// Method 1: Sorting
  6. 	// Time: O(n * log(n)), Space: O(1)
  7. 	// sort(nums.begin(), nums.end());
  8.  
  9. 	// Method 2: Counting 0s, 1s and 2s
  10. 	// Time: O(n), Space: O(n)
  11. 	// int zeros = 0, ones = 0, twos = 0;
  12. 	// for (int i = 0; i < nums.size(); i++) {
  13. 	// 	switch (nums[i]) {
  14. 	// 		case 0:
  15. 	// 			zeros++;
  16. 	// 			break;
  17. 	// 		case 1:
  18. 	// 			ones++;
  19. 	// 			break;
  20. 	// 		case 2:
  21. 	// 			twos++;
  22. 	// 			break;
  23. 	// 	}
  24. 	// }
  25. 	// for (int i = 0; i < zeros; i++) {
  26. 	// 	nums[i] = 0;
  27. 	// }
  28. 	// for (int i = zeros; i < zeros + ones; i++) {
  29. 	// 	nums[i] = 1;
  30. 	// }
  31. 	// for (int i = zeros + ones; i < nums.size(); i++) {
  32. 	// 	nums[i] = 2;
  33. 	// }
  34.  
  35. 	// Method 3: Dutch National Flag Algorithm
  36. 	// Time: O(n), Space: O(1)
  37. 	int low = 0, mid = 0, high = nums.size() - 1;
  38. 	while (mid <= high) {
  39. 		switch (nums[mid]) {
  40. 			case 0:
  41. 				swap(nums[low], nums[mid]);
  42. 				low++;
  43. 				mid++;
  44. 				break;
  45. 			case 1:
  46. 				mid++;
  47. 				break;
  48. 			case 2:
  49. 				swap(nums[mid], nums[high]);
  50. 				high--;
  51. 				break;
  52. 		}
  53. 	}
  54. }
  55.  
  56. void print(vector<int> &nums) {
  57. 	for (int i = 0; i < nums.size(); i++) {
  58. 		cout << nums[i] << " ";
  59. 	}
  60. 	cout << endl;
  61. }
  62.  
  63. int main() {
  64. 	int n;
  65. 	cin >> n;
  66. 	vector<int> nums(n);
  67. 	for (int i = 0; i < n; i++) {
  68. 		cin >> nums[i];
  69. 	}
  70. 	solve(nums);
  71. 	print(nums);
  72. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
6
2 1 2 0 1 0
stdout
copy 
0 0 1 1 2 2
https://ideone.com/8KUXOw
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!