从给定数字中找到下一个最高的独特数字

Question

给定一个包含 n 个符号和一个长度为 k 的组合，组合中的字符不重复来自符号集合。编写一个仅使用迭代算法的程序，打印出可以生成的下一个最高独特数字。

例如：

Symbols =[1,2,3,4,5]
size = 3;
given combination = 123, result = 124
given combination = 254, result = 312

- Kshitij Banerjee

---

好的面试官能够判断你是否使用了套路回答。如果你需要思考回答，他们会更喜欢，因为他们可以看到你的解决问题的过程，这比仅仅知道答案更加重要。 - Almo

123 可用: 45 检查 3..替换为 4对于 254 可用:13 检查 4..1,3<4 将 4 放入可用 检查 5..不可用 检查 2..可用: 1345 将 2 插入可用，替换为 3，然后跟随 1 和 2 - Kshitij Banerjee

我可能会使用TreeSet而不是队列，因为你始终从开头迭代。否则，那就是我提出的解决方案。 - Stefan

我将对组合数字进行编码和解码。（为每个可能的组合分配一个数字）这样做会使递增变得微不足道。 - Peter Lawrey

@Stefan 使用TreeSet并不会更有效率，因为需要查看队列的两端以进行优化。 - NominSim

Answer 1

当您在迭代（向后）跨越数字时，您不必每次都检查最低可用数字，而是可以将上次检查的数字与当前数字进行比较。如果小于上次，则跳过下一个数字并将当前数字添加到可用数字中；如果大于上次，则检查可用数字以找到可能的最低数字（高于当前数字），并使用队列中的最低数字填充其余数字。

i.e. 254

current = 4      // 4 < 1,3  so no higher available
last_checked = 4 // available = {1, 3, 4}
current = 5      // 4 < 5 so no higher available
last_checked = 5 // available = {1, 3, 4, 5}
current = 2      // 5 > 2 so search available for lowest possible(higher than 2) = 3
set 3,_,_        // Then just add lowest elements until full: 3,1,2 = 312

这样你只需查看可用的符号一次，最多比较k次。

- NominSim

Answer 2

这里有一个伪代码算法来完成这个任务：

int n = length(Symbols);
int k = length(A);
// TRACK WHICH LETTERS ARE STILL AVAILABLE
available = sort(Symbols minus A);
// SEARCH BACKWARDS FOR AN ENTRY THAT CAN BE INCREASED
for (int i=k-1; i>=0; --i) {
    // LOOK FOR NEXT SMALLEST AVAILABLE LETTER
    for (int j=0; j<n-k; ++j) {
        if (A[i] < available[j]) {
            break;
        }
    }
    if (j < n-k) {
        // CHANGE A[i] TO THAT, REMOVE IT FROM AVAILABLE
        int tmp = A[i];
        A[i] = available[j];
        available[j] = tmp;
        // RESET SUBSEQUENT ENTRIES TO SMALLEST AVAILABLE
        for (j=i+1; i<k; ++j) {
            A[j] = available[i+1-j];
        }
        return A;
     } else {
         // A[i] MUST BE LARGER THAN AVAILABLE, SO APPEND TO END
         available = append(available,A[i]);
     }
}

- PengOne

---

我给了相同的答案！面试官说我可以更优化它！！请看我的帖子上的评论！ - Kshitij Banerjee

Answer 3

public class IncrementSybmols {
    public static void main(String[] args) throws Throwable {
        List<Integer> syms = Arrays.asList(1,2,3,4,5);

        test(syms, 3, Arrays.asList(1,2,3), Arrays.asList(1,2,4));
        test(syms, 3, Arrays.asList(2,5,4), Arrays.asList(3,1,2));

        test(syms, 3, Arrays.asList(4,3,5), Arrays.asList(4,5,1));
        test(syms, 3, Arrays.asList(5,4,2), Arrays.asList(5,4,3));
        test(syms, 3, Arrays.asList(5,4,3), null);
    }

    private static void test(List<Integer> syms, int n, List<Integer> in, List<Integer> exp) {
        List<Integer> out = increment(syms, n, in);
        System.out.println(in+" -> "+out+": "+( exp==out || exp.equals(out)?"OK":"FAIL"));
    }

    private static List<Integer> increment(List<Integer> allSyms, int n, List<Integer> in){
        TreeSet<Integer> availableSym = new TreeSet<Integer>(allSyms);
        availableSym.removeAll(in);

        LinkedList<Integer> current = new LinkedList<Integer>(in);

        // Remove symbols beginning from the tail until a better/greater symbols is available.
        while(!current.isEmpty()){
            Integer last = current.removeLast();
            availableSym.add(last);

            // look for greater symbols
            Integer next = availableSym.higher(last);
            if( next != null ){
                // if there is a greater symbols, append it
                current.add(next);
                availableSym.remove(next);
                break;
            }
        }

        // if there no greater symbol, then *shrug* there is no greater number
        if( current.isEmpty() )
            return null;

        // fill up with smallest symbols again
        while(current.size() < n){
            Integer next = availableSym.first();
            availableSym.remove(next);
            current.add(next);
        }

        return current;
    }
}

- A.H.

Answer 4

试试这个方法：

public int nextCombo(int[] symbols, int combo, int size) {
    String nc = "";
    symbols = java.util.Arrays.sort(symbols);
    for (int i = 0; i < size; i++) nc += Integer.toString(symbols[symbols.length - 1]);
    if (Integer.parseInt(nc) == combo) return combo; //provided combo is the largest possible so end the method
    nc = "";
    int newCombo = 0;
    while (newCombo < combo) { //repeat this process until the new combination is greater than the provided one
        for (int i = 0; i < size; i++) { //keep appending numbers from the symbol array onto the new combo until the size limit is reached
            nc += Integer.toString(symbols[(int) Math.floor(Math.random() * size)]);
        }
        newCombo = Integer.parseInt(nc);
    }
    return newCombo;
}

- fireshadow52