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

chả cần làm gì cao siêu, sort này nọ, chỉ cần hash map là đc mà
https://play.golang.org/p/5dOvtnepj7x

Code:
package main

import (
    "fmt"
    "sort"
    "strconv"
)

func main() {
    fmt.Println("Hello, playground")
    arr := []int{1, 2, 9, 134, 12, 1}
    fmt.Println(sortLength(arr))
}

func sortLength(arr []int) []int {
    lengthMap := make(map[int][]int)
    keysMap := make(map[int]bool, 0)

    var result []int
    for _, v := range arr {
        lengthInt := len(strconv.Itoa(v))
        lengthMap[lengthInt] = append(lengthMap[lengthInt], v)
        keysMap[lengthInt] = true
    }
    var keys []int
    for i, v := range keysMap {
        if v == true {
            keys = append(keys, i)
        }
    }
    sort.Ints(keys)

    for _, k := range keys {
        result = append(result, lengthMap[k]...)
    }
    return result
}
Bài này đâu cần sort keys, chỉ cần chạy từ 1 -> 10 là đc, bỏ 1 loop 1 sort là đẹp.
 
bác này nói có lý này,thật cái vụ bigO nó chỉ có ý nghĩa khi số lượng phần tử phải rất lớn ( tầm hơn 1tr) lúc này ta mới có thể xem các phép tính trong 1 vòng lặp là không đáng kể và gần như là bằng nhau. -> thường thuật toán này quan trọng khi xử lý big data.

Còn thường nếu không phải là big data, thì sự khác biệt việc giữa O(n) vs O(n^2) có thể không đáng kể mà dùng quicksort có sắn trong nhiều ngôn ngữ vs tường mình hơn hẳn

Tính ko nói đâu nhưng tới đây thì phải chêm vài câu.
Bác bảo ko quan tâm BigO vậy phải đặt context ở đây là gì.
bác thớt đưa 1 bài ra để thảo luận. Bài thì có nhiều cách làm, mình thấy bạn Trung kia quan tâm vấn đề space + complexity là điều hay với những bài như thế này.

nếu ko thảo luận về space và complexity thì mình cũng ko biết các bác thảo luận cái gì trong 1 topic như thế này?

Tất nhiên đề bài ko rõ ràng, mình nói ví dụ limit về số lượng phần tử trong mảng, hay limit về độ lớn của số, big int hay int32, int64.

Những cái đó mở nên thảo luận thêm cũng sẽ học dc nhiều cái hay. Ví dụ các bác xử lý thế nào với số lớn?

anw bạn Trung mình thấy dù comment đầu trong topic này có thể khiến bác thớt khó chịu, nhưng bạn ấy đã xin lỗi + thái độ rất cầu thị.
Mình nghĩ đó là tinh thần mọi ng nên có.
 
cái này ko phải sort nhé mn, cái này là sort.Ints nhé. I'm done

thực ra tôi chỉ sort trên keys tức là một tập rất nhỏ, có size <= max length của input thôi (nếu requirements cho input có size max là 10 thì mảng keys chỉ có tối đa 10 elements

sở dĩ làm cách này vì chủ thớt ko cho rõ input giới hạn như nào, max length bao nhiêu, chứ nếu ko tôi loop 1 phát từ 1-10 như bác @trungpham90 là xong rồi.

cốt yếu ý tưởng bài toán chẳng có gì khó, chỉ là map lại length vào hashmap rồi loop từ key nhỏ nhất đến lớn nhất append vào array kết quả là xong. Sao không bình luận chỗ đấy mà săm soi việc xử lý input nhỉ :LOL:

Bài này đâu cần sort keys, chỉ cần chạy từ 1 -> 10 là đc, bỏ 1 loop 1 sort là đẹp.
 
Back
Top