主页 / coding / 问题 / 79490590
Accepted
CodeCrusader
Asked: 2025-03-07 04:17:07 +0800 CST

找到排序顺序的最少操作

  • 772

任务描述为：

我有一个从 1 到 n 的不同数字数组，例如 arr = [5, 3, 4, 1, 2]

将名为 order 的变量初始化为 1，现在从左到右遍历数组并查找与变量 order 匹配的元素，如果找到则增加 order 并向前移动。换句话说，我们可以说将名为 order 的变量初始化为 1，因此首先从左到右遍历数组并查看 1 在数组中出现的位置，然后将 order 增加到 2，然后在数组中向前移动并查找 2，如果找到则将 order 增加到 3。像上面那样从左到右迭代称为操作

当 arr = [5,3,4,1,2] 时，从左到右依次遍历，当找到 arr[3] 时，order 的值从 1 变为 2，当找到 arr[4] 时，order 的值从 2 变为 3

重复上述步骤，直到变量阶达到值n。重复的次数称为操作。

因此当 arr [ 5,3,4,1,2] 时，所需的最少操作数为 3

import java.util.*;

class Main {
    public static int solve(List<Integer> arr) {
        int n = arr.size();
        int order = 0; // Number of sorted items found
        int operations = 0;  // Count of full array scan
        
        while (sortedCount < n) {
            order++;
            for (int i = 0; i < n; i++) {
                if (arr.get(i) == order + 1) {
                    order++;
                }
            }
        }        
        return operations;
    }

    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(5, 3, 4, 1, 2))); // Output: 3
        System.out.println(solve(Arrays.asList(3,1,4,2,5))); // Output: 2
        System.out.println(solve(Arrays.asList(1,2,3,4))); // Output: 1
        System.out.println(solve(Arrays.asList(2,1))); // Output: 2
    }
}

我的代码运行时间为 O(n^2)，我们如何才能以更低的时间复杂度解决这个问题

java

3 个回答

  1. Best Answer

    以下算法在 O(n) 中解决问题：

    public static int solve(List<Integer> arr) {
    int operations = 0;
    Set<Integer> visited = new HashSet<>();
    for (int i : arr) {
        if (!visited.contains(i - 1))
           operations++;
        visited.add(i);
    }
    return operations;
}

    这个想法是，如果你之前没有看到数字 - 1，那么你必须在下一次传递中得到它，所以这是计算所有必需的传递。你可以使用布尔数组代替哈希集来提高性能，但复杂性是一样的。

    • 3

  2. 这是我的想法

        public static int solve(List<Integer> arr) {
        int n = arr.size();
        Map<Integer, Integer> indexMap = new HashMap<>();
        
       
        for (int i = 0; i < n; i++) {
            indexMap.put(arr.get(i), i);
        }
        // we store
        //5 -> 0  
        //3 -> 1  
        //4 -> 2  
        //1 -> 3  
        //2 -> 4  
        
        int operations = 1; //we start from 1
        for (int i = 2; i <= n; i++) { // and try to find each next number (2, 3, 4, ...).
            //If index of i is bigger than index of (i - 1), we’re still good, Numbers are appearing in increasing order
            if (indexMap.get(i) < indexMap.get(i - 1)) {
                operations++; //BUT if index of i is smaller, that means we gotta restart our search (new operation needed).
            }
        }
        //One loop to build the map (O(n))
        //One loop to count operations (O(n))
        // => Total: O(n)
        return operations;
    }
    • 1

  3. 如果数组包含数字 1 到 N，那么您可以按照所需的排序顺序打印数字 1 到 N，而无需查看数组。

    • -3

相关问题