thắc mắc Bài toán sắp xếp, làm thế nào cho hay?

rosario_1

Member
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134

Không khó nhưng làm thế nào để code cho hay đây?
 
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134

Không khó nhưng làm thế nào để code cho hay đây?

Thím xây dựng hàm Compare (so sánh) theo tiêu chí của đề bài.
Rồi căn cứ theo hàm so sánh ấy áp dụng Quick Sort, Merge Sort hay Heap Sort đều OK! :)
 
Tạo 1 cái list 2 chiều. Dòng 0 chứa các số có 1 chữ số, dòng 1 chứa các số 2 chữ số... Dùng 1 vòng for là xong.
Demo = c#.
PHP:
        static void Main(string[] args)
        {
            int[] arr = { 1,2,9,134,12,1  };
            List<int>[] r = new List<int>[10];
            foreach (var n in arr)
            {            
               var index = Count(n);
                if (r[index] == null)
                {
                    r[index] = new List<int>();
                    r[index].Add(n);
                }
                else r[index].Add(n);
            }
            Display(r);
            ReadKey();
        }
        static int Count(int n)
        {
            int r = 0;
            while (n >= 10)
            {
                n /= 10;
                r++;
            }
            return r;
        }
        static void Display(List<int>[] r)
        {
            for (int i = 0; i < r.Length; i++)
                if (r[i] != null)
                    foreach (var n in r[i])
                        Console.WriteLine(n);
        }
   
[I][I][\PHP][/I][/I][/Quote]
 
Last edited:
Đề bài hơi khó hiểu nhỉ, theo mình hiểu thì ouput thế này mới đúng:
Output: 1,1,12,134,2,9
Rào trước: không bash, không chửi, không nói có gì mà khó hiểu, okay?
 
Đề bài hơi khó hiểu nhỉ, theo mình hiểu thì ouput thế này mới đúng:
Output: 1,1,12,134,2,9
Rào trước: không bash, không chửi, không nói có gì mà khó hiểu, okay?

Đề này so sánh số chữ số thôi, số nào nhiều chữ số hơn thì đứng sau. Các số có cùng số chữ số thì xem số nào đứng trước trong đề bài thì sẽ xếp trước.
 
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134


Không khó nhưng làm thế nào để code cho hay đây?

Cái ví dụ sai hay sao vậy? Phải là thế này chứ:

Input: 1,2,9,134,12,-11
Output: 1,2,9,-11,12,134


Hay là số đã có trong dãy 1 thì sẽ nằm đầu dãy 2, chứ ko nằm trong dãy 1 nữa ??
 
Thím xây dựng hàm Compare (so sánh) theo tiêu chí của đề bài.
Rồi căn cứ theo hàm so sánh ấy áp dụng Quick Sort, Merge Sort hay Heap Sort đều OK! :)
Đây là cách tớ làm trên thực tế. Chỉ có điều tớ chưa cảm thấy thỏa mãn với cái cách tớ làm, nó hơi thô chưa được "đẹp". Bạn cho xin code cụ thể, tớ muốn tham khảo cách b
 
Counting sort/ radix sort nhé. Tham khảo rồi modify cho phù hợp. Bài tập về nhà à?
Ko bạn, tớ đi làm từ lâu lắm lắm rồi, đây chỉ đơn giản vừa là giải trí vừa là tự nâng cấp skill thuật toán. Tớ đọc Counting sort/ radix sort thì thấy không phải giải pháp, vì yêu cầu sắp xếp của mình có dựa vào cả thứ tự ban đầu nên không work, bạn thử cho code chạy thử xem thế nào.
 
Chuyển các số về số chữ số rồi sort trên dãy mới. 1,2,9,134,12,1 -> 1,1,1,3,2,1 -> sort -> output (chọn cái sort nào nó giữ nguyên thứ tự ấy.)
 
Ko bạn, tớ đi làm từ lâu lắm lắm rồi, đây chỉ đơn giản vừa là giải trí vừa là tự nâng cấp skill thuật toán. Tớ đọc Counting sort/ radix sort thì thấy không phải giải pháp, vì yêu cầu sắp xếp của mình có dựa vào cả thứ tự ban đầu nên không work, bạn thử cho code chạy thử xem thế nào.
Anh tự nghĩ đi, radix sort thì anh đổi sort từ least significant digit (LSD) -> (most significant digit) MSD sang sort từ MSD -> LSD là xong, có cái j khó, radix sort là stable sort, ko hiểu sao lại ko giữ đc thứ tự? Bài để anh làm cho giỏi lại bắt tôi code thì làm làm j?
 
func sapxep(array ar) {
for(i = 0 -> ar.length) {
for(j = i + 1 -> ar.length) {
if(ar [ i ] .length > ar [ j ] . length) {
tem = ar [ i ];
ar [ i ] = ar[ j ];
ar[j] = tem;
}
}
}
}
 
CPP version:
Code:
void stupidSort(vector<int>& nums) {
    vector<int> idx(nums.size());
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int k) {return floor(log10(nums.at(i))) < floor(log10(nums[k])) || (i < k);});
    vector<int> temp;
    temp.reserve(nums.size());
    for (auto i : idx) {
        temp.emplace_back(nums[i]);
    }
    std::copy(temp.begin(), temp.end(), nums.begin());
}
 
Last edited:
C#:
static void Main(string[] args)
        {
            List<int> cin = new List<int>() { 1, 2,1234, -44,9, 134, 12, 1,-11, };
            int maxLength = cin.Max().ToString().Length;
            int length = 1;
            
            Console.WriteLine(string.Join(",", swap(cin, length, maxLength)));
            Console.ReadLine();
        }
        public static List<int> swap(List<int> cin, int length, int maxLength)
        {
            List<int> cout = new List<int>();
            for (int i = 0; i < cin.Count; i++)
            {
                if ((cin[i] < 0 && (cin[i] * -1).ToString().Length == length) || (cin[i] > 0 && cin[i].ToString().Length == length))
                {
                    cout.Add(cin[i]);
                }
            }
            if(length < maxLength)
            {
                cout.AddRange(swap(cin, length + 1, maxLength));
            }
            return cout;
        }
 
Cho 1 dãy số tự nhiên. Hãy sắp xếp theo thứ tự từ bé đến lớn theo số chữ số. Nếu số chữ số như nhau thì số đứng trước trong dãy ban đầu sẽ đứng trước.

Input: 1,2,9,134,12,1
Output: 1,2,9,1,12,134

Không khó nhưng làm thế nào để code cho hay đây?
C:
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
#include <math.h>

int values[] = {  1,2,9,134,12,1 };

int stupid_compare (const void * a, const void * b)
{
  return ( log10(*(int*)a) - log10(*(int*)b ));
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), stupid_compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

1591266056919.png

http://cpp.sh/9ngoh
1aaZtCp.png
 
C:
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
#include <math.h>

int values[] = {  1,2,9,134,12,1 };

int stupid_compare (const void * a, const void * b)
{
  return ( log10(*(int*)a) - log10(*(int*)b ));
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), stupid_compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}
View attachment 80182
http://cpp.sh/9ngoh
1aaZtCp.png
thử testcase này đi
[1,10,9,134,12,1]
 
thử testcase này đi
[1,10,9,134,12,1]
Sửa lại

thử testcase này đi
[1,10,9,134,12,1]
Fixed : Quên chưa ép kiểu về int

C:
/* qsort example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
#include <math.h>

int values[] = { 1,10,9,134,12,1 };

int stupid_compare (const void * a, const void * b)
{
  return ( (int)log10(*(int*)a) - (int)log10(*(int*)b ));
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), stupid_compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}
 
Back
Top