时间戳

首页 > 解决方案 > 如何降低代码的时间复杂度？

java - 如何降低代码的时间复杂度？

问题描述

我已经给队列初始位置增加了 1，从行前的 1 到后面的n。

队列中的任何人都可以贿赂直接排在他们前面的人以交换位置。如果两个人交换位置，他们仍然会佩戴相同的标签，表示他们原来的位置。一个人最多可以贿赂另外两个人。例如，如果n = 8 且Person 5贿赂Person 4，则队列将如下所示：1,2,3,5,4,6,7,8。

minimumbribes必须打印一个整数，表示创建原始队列所需的最小贿赂数，或者如果行配置不可行，则太混乱。如果一个人的贿赂数量不超过 2，那么线路配置是不可能的。

minimumBribes 具有以下参数：

样本输入

2
5
2 1 5 3 4
5
2 5 1 3 4

输出

3
Too chaotic

使用排序逻辑，我刚刚计算了来得早的人，并且大于跟随的人。如果线路配置可能，它还会打印贿赂总数，否则它会打印太混乱的消息。 

static void minimumBribes(int[] q) {
    int count = 0; // Counts the no of bribes by an individual.
    int j;
    int total = 0; // Total no of bribes.

   loop1 : for(int i = 0; i < q.length; i++) {
      loop2 :  for(j = i; j < q.length; j++) {
            if(q[i] > q[j]) {
                count++;
                if(count > 2) {
                    System.out.println("Too chaotic");
                    break loop1;
                }

            }
            else if (q[i] <= q[j]) {
                total += count;
                count = 0;

            }
        }
    }
    if(count <= 2)    
    System.out.println(total);
}

上面提到的代码非常适合小队列运行，但是如果数组的大小很大，则超过了处理的固定时间限制。

标签： javaperformancetime-complexity

解决方案

我刚刚在 python 中解决了这个问题，以便更好地理解这个问题。

我决定从队列中的最后一个人开始，因为我们可以立即对这个人说很多事情：

  1. 他们只能向前贿赂（即他们背后没有人贿赂他们）
  2. 他们不能贿赂到距离“EOQ”超过两个位置的位置 [，其中 EOQ 表示队列结束或此人的初始位置]。

我们可以从一个人N到另一个人将这个规则应用到每个人身上1。

伪代码：

FOR PERSON in [N to 1]:
  P = PERSON
  IF (P MORE THAN 2 POSITIONS FROM INITIAL POS; OR P IS FURTHER BACK IN QUEUE):
    PRINT 'Too chaotic'
    RETURN

  FOR POS in [CURR_POS[P] to INIT_POS[P]]:     
     SWAP POSITION OF P AND PERSON_TO_THE_RIGHT_OF_P
     INCREMENT COUNT OF BRIBES BY 1

PRINT COUNT_OF_BRIBES

笔记

  • INIT_POS[P]指在任何贿赂发生之前该人的初始位置，所以INIT_POS[PERSON_5] = 5

  • CURR_POS[P]指P算法开始时或任何交换之后的当前位置。

  • 在这个算法的最后，（假设贿赂不是混乱的）以下不变量应该成立CURR_POS[i] == i：原因是因为我们所做的只是在贿赂发生之前让所有人回到原来的位置。

推荐阅读