求效率的演算法？

01-13

有一個字元串，比如aaabccddd最後輸出abcdacdad, 比如addsggg輸出adgsdgg,原理你們都懂得，用什麼演算法思想可以解決的更為高效？
------------

(⊙o⊙)…，大概是這樣：先找出互不重複的所有字元，排序輸出，（所以是adgs 不是 adsg）剩下來的字元處理方式規則和前面一樣。
（如果帶上『0』-『9』）007799aabbccddeeff113355zz ---- 013579abcdefz013579abcdefz這個例子應該很明顯了

是hihoCode今晚的題嗎？

我是先把輸入的string掃一遍，存到一個10+26的int數組裡，每個int表示對應的數字或者字母總共出現過的次數，然後再遍曆數組，輸出值不為0的數組下標所對應的數字或字母，因為第一個輸出的segment肯定是最大字串，然後每列印一個把對應數組的值--，基本屬於用空間換時間，能ac，最後找不為0的數組過程可以進一步優化

其實就是個轉置嘛, 和矩陣轉置很像， Haskell 裡面一行就寫完了。

transform = concat . transpose . group . sort

完整代碼要2行.

import Data.List main = putStr . concat . transpose . group . sort =&<&< getLine

把aaabccddd處理成((a,3),(b,1),(c,2),(d,3))

string Transform(string input) { var xs = (from x in input groupby x into g orderby g.Key select Tuple.Create(g.Key,g.Count())).ToArray(); var max = (from x in xs select x.Item2).Max(); return (from i in Enumerable.Range(0, max) select new string(from x in xs where x.Item2&>i select x.Item1)).Aggregate((a,b)=&>a+b); }

說下思路，建立一個128（對應每個字元）位長度的數組，存放每個字元出現的次數，剩下的就是列印了數組中值不為0對應的字元。。。。

由於列印時需要不停遍歷這個128位的數組，所以，增加步長概念，每次不再移動一位。。。

VS壞掉了，最後只好用記事本寫了（加入步長實現，折騰了很久），找了一個在線網站，編譯了下發現能通過，就發出來了。。。

可讀性不太好（一切為了性能），輕噴，也期待更高效的實現

-----------------------------------------

#include & void Transform(const char *str, int len) { int char_count[128] = {0}; int step_len[128]; for (int i = 0; i &< 128; i++) step_len[i] = 1; for (int i = 0; i &< len; i++) char_count[(int)str[i]]++; char *tmpstr = (char*)malloc(len+1); tmpstr[len+1-1] = 0; int n = 0; int i = 0; int k = (i-1)127; while (n &< len) { if (char_count[i] &> 0) { tmpstr[n] = i; char_count[i]--; n++; k = i; } else { step_len[k] += step_len[i]; } i = ((i+step_len[i])127); } printf("result: %s ", tmpstr); free(tmpstr); }

int main() { const char *str = "007799aabbccddeeff113355zz"; int len = strlen(str); Transform(str, len); return 0; }

統計所有字元，用環形的鏈表串起來，然後不斷的輸出鏈表裡的字元，

被掃過一次遞減，減到零的刪節點，全部被刪結束。

本來我以為猜出「原理你們都懂的」究竟是怎麼回事了。但發現第二個答案居然是adgsdgg而不是adsgdgg，那就只能假設如果題主不是個粗心的二貨，那就是我不屬於「你們都懂的」了。

環形緩衝，或者映射成二維數組

構建鏈表，我覺得是最高效的了。代碼不是很美，輕噴。

#include & #include & #include &


struct list_node {

        int n;

        char c;

        struct list_node *prev;

        struct list_node *next;

};
struct list_node * list_node_new()

{

        struct list_node *node = NULL;

        node = (struct list_node *)calloc(1, sizeof(struct list_node));

        if (!node) {

                return NULL;

        }
        node-&>prev = node;

        node-&>next = node;
        return node;

}
void list_node_free(struct list_node *node)

{

        free(node);

}
void list_insert(struct list_node *head, char c)

{

        struct list_node *cur = head;

        while (cur-&>next != head  cur-&>next-&>c &< c) {
                cur = cur-&>next;

        }
        if (cur-&>next == head ||  cur-&>next-&>c &> c) {

                struct list_node *new_node = list_node_new();

                new_node-&>c = c;

                new_node-&>n = 1;

                new_node-&>next = cur-&>next;

                new_node-&>prev = cur;

                cur-&>next-&>prev = new_node;

                cur-&>next = new_node;

        } else if (cur-&>next-&>c == c) {

                cur-&>next-&>n++;

        }

}
void list_delete_node(struct list_node *head, struct list_node *node)

{

        node-&>prev-&>next = node-&>next;

        node-&>next-&>prev = node-&>prev;

        list_node_free(node);

}
void list_print(struct list_node *head, int n)

{

        struct list_node *cur = head-&>next;

        while (n &> 0) {

                if (cur != head) {

                        printf("%c", cur-&>c);

                        if (--cur-&>n == 0) {

                                cur = cur-&>next;

                                list_delete_node(head, cur-&>prev);

                        } else {

                                cur = cur-&>next;

                        }

                        n--;

                } else {

                        cur = cur-&>next;

                }

        }

        printf("

");

}
int main(int argc, char *argv[])

{

        struct list_node *head = list_node_new();

        char str[1000] = {0};

        char *s = str;

        int n = 0;
        scanf("%s", str);

        while (*s != "") {

                list_insert(head, *s++);

                n++;

        }
        list_print(head, n);

        list_node_free(head);

return 0; }

親測有效：

def transform(s): d = sorted([(c, s.count(c)) for c in set(list(s))]) l = max(d, key=lambda k: k[1])[1] return "".join(c for i in range(1, l+1) for c, n in d if i &<= n)