LeetCode 1528. 重新排列字符串

柔光的暖阳◎ 2023-03-02 05:17 20阅读 0赞

给你一个字符串 s 和一个 长度相同 的整数数组 indices 。

请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices\[i\] 指示的位置。

返回重新排列后的字符串。

输入：s = “codeleet”, indices = \[4,5,6,7,0,2,1,3\]  
输出：“leetcode”  
解释：“codeleet” 重新排列后变为 “leetcode” 。

法一：原地排序，时间复杂度为O（n），思路是遍历字符串s，每遍历到一个字符，查找该字符应该在的位置，之后交换该字符和它应该在的位置的字符，然后将indices中它应在的位置下标取负，代表该位置已经排好序了。之后记录下被交换的字符的下标，以查找该字符应在的下标，重复以上过程：

class Solution { 
    public:
        string restoreString(string s, vector<int>& indices) { 
            int sz = s.size();
            for (int i = 0; i < sz; ++i) { 
                int j = i;
                while (indices[j] > 0) { 
                    swap(s[i], s[indices[j]]);
                    indices[j] = -indices[j];
                    j = -indices[j];
                }
            }
            return s;
        }
    };

以上过程遍历到一个应在下标0位置的元素时，不会将该元素放到下标0处，当其他元素都在自己应在的位置时，下标0的元素自然也在自己应在的位置了。

法二：空间O（n）解法：

class Solution { 
    public:
        string restoreString(string s, vector<int>& indices) { 
            string res;
            int sz = s.size();
            res.resize(sz);
            for (int i = 0; i < sz; ++i) { 
                res[indices[i]] = s[i];
            }
            return res;
        }
    };