查找由数组的数字组成的最大数字
Find largest number formed with numbers of an array
任务是找出数组中的数字组成的最大数字。例如:
输入:7、56、94、1
输出:947561
在代码中,我比较了 ab 和 ba,然后使用冒泡排序对数字进行排序。
我的代码适用于 80% 的测试用例,但我找不到错误。我在哪里或哪种情况没有考虑到?提前致谢。
#include <iostream>
#include <cmath>
using namespace std;
typedef long long int ll;
ll len(ll n){
ll l = 0;
while (n > 0){
n /= 10;
l++;
}
return l;
}
ll concade(ll a, ll b){
ll con = a * pow(10, len(b)) + b;
return con;
}
void swap(ll *xp, ll *yp){
ll temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubble_sort(ll arr[], ll n){
ll i, j;
for (i = 0; i < n - 1; i++){
for (j = 0; j < n-i-1; j++){
if (arr[j] == 0 && arr[j+1] != 0)
swap(arr[j], arr[j+1]);
if (concade(arr[j], arr[j+1]) < concade(arr[j+1], arr[j]))
swap(arr[j], arr[j+1]);
}
}
}
int main(){
ll n;
while (cin >> n){
if (n == 0)
break;
ll arr[1000000];
for(ll i = 0; i < n; i++){
ll x;
cin >> x;
arr[i] = x;
}
bubble_sort(arr, n);
for (ll i = 0; i < n; i++)
cout << arr[i];
cout << endl;
}
}
贪心法很适合你的问题。
- 根据第一个不同的数字对数字进行排序。
- 合并它们(降序排列)
这是 C# 中的实现(语法相似)
注意:您可以对大型数据集使用字符串,对小型数据集使用数字。并考虑使用更快的算法进行排序而不是冒泡排序
private static long F(List<int> numbers)
{
// 1
for (int i = 0; i < numbers.Count; i++)
{
for (int j = 0; j < numbers.Count; j++)
{
if (Compare(numbers[i], numbers[j]) > 0)
{
var temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
}
// 2
long bigNumber = 0;
for (int i = 0; i < numbers.Count; i++)
{
int numberOfDigits = NumberOfDigits(numbers[i]);
bigNumber = (bigNumber * Pow10(numberOfDigits));
bigNumber += numbers[i];
}
return bigNumber;
}
private static long Compare(long n1, long n2)
{
while (n1 > 0 && n2 > 0)
{
var difference = FirstDigit(n1) - FirstDigit(n2);
if (difference != 0)
{
return difference;
}
n1 %= Pow10(NumberOfDigits(n1) - 1);
n2 %= Pow10(NumberOfDigits(n2) - 1);
}
return FirstDigit(n1) - FirstDigit(n2);
}
private static long Pow10(long times)
{
long s = 1;
for (int i = 0; i < times; i++)
{
s *= 10;
}
return s;
}
private static long FirstDigit(long n)
{
while (n >= 10)
{
n /= 10;
}
return n;
}
private static int NumberOfDigits(long n)
{
int digits = 1;
while (n >= 10)
{
digits++;
n /= 10;
}
return digits;
}
这是使用 C# 特殊语法的解决方案:
private static string F(List<int> numbers)
{
return string.Join("", numbers
.Select(x => x.ToString())
.OrderByDescending(x => x));
}
任务是找出数组中的数字组成的最大数字。例如:
输入:7、56、94、1 输出:947561
在代码中,我比较了 ab 和 ba,然后使用冒泡排序对数字进行排序。
我的代码适用于 80% 的测试用例,但我找不到错误。我在哪里或哪种情况没有考虑到?提前致谢。
#include <iostream>
#include <cmath>
using namespace std;
typedef long long int ll;
ll len(ll n){
ll l = 0;
while (n > 0){
n /= 10;
l++;
}
return l;
}
ll concade(ll a, ll b){
ll con = a * pow(10, len(b)) + b;
return con;
}
void swap(ll *xp, ll *yp){
ll temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubble_sort(ll arr[], ll n){
ll i, j;
for (i = 0; i < n - 1; i++){
for (j = 0; j < n-i-1; j++){
if (arr[j] == 0 && arr[j+1] != 0)
swap(arr[j], arr[j+1]);
if (concade(arr[j], arr[j+1]) < concade(arr[j+1], arr[j]))
swap(arr[j], arr[j+1]);
}
}
}
int main(){
ll n;
while (cin >> n){
if (n == 0)
break;
ll arr[1000000];
for(ll i = 0; i < n; i++){
ll x;
cin >> x;
arr[i] = x;
}
bubble_sort(arr, n);
for (ll i = 0; i < n; i++)
cout << arr[i];
cout << endl;
}
}
贪心法很适合你的问题。
- 根据第一个不同的数字对数字进行排序。
- 合并它们(降序排列)
这是 C# 中的实现(语法相似)
注意:您可以对大型数据集使用字符串,对小型数据集使用数字。并考虑使用更快的算法进行排序而不是冒泡排序
private static long F(List<int> numbers)
{
// 1
for (int i = 0; i < numbers.Count; i++)
{
for (int j = 0; j < numbers.Count; j++)
{
if (Compare(numbers[i], numbers[j]) > 0)
{
var temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
}
// 2
long bigNumber = 0;
for (int i = 0; i < numbers.Count; i++)
{
int numberOfDigits = NumberOfDigits(numbers[i]);
bigNumber = (bigNumber * Pow10(numberOfDigits));
bigNumber += numbers[i];
}
return bigNumber;
}
private static long Compare(long n1, long n2)
{
while (n1 > 0 && n2 > 0)
{
var difference = FirstDigit(n1) - FirstDigit(n2);
if (difference != 0)
{
return difference;
}
n1 %= Pow10(NumberOfDigits(n1) - 1);
n2 %= Pow10(NumberOfDigits(n2) - 1);
}
return FirstDigit(n1) - FirstDigit(n2);
}
private static long Pow10(long times)
{
long s = 1;
for (int i = 0; i < times; i++)
{
s *= 10;
}
return s;
}
private static long FirstDigit(long n)
{
while (n >= 10)
{
n /= 10;
}
return n;
}
private static int NumberOfDigits(long n)
{
int digits = 1;
while (n >= 10)
{
digits++;
n /= 10;
}
return digits;
}
这是使用 C# 特殊语法的解决方案:
private static string F(List<int> numbers)
{
return string.Join("", numbers
.Select(x => x.ToString())
.OrderByDescending(x => x));
}