嵌套while循环的java时间复杂性？

Question

我在做一个面试准备问题，我必须添加一系列时间给我的时间。我有两个循环，一个用于解析时间，另一个用于将分钟与秒分开。我认为这两个嵌套循环使时间复杂度为O（n^2）。我的室友告诉我这是一个糟糕的代码，可以在O（n）时间内解决，但我不知道如何解决。任何帮助都将不胜感激。提前谢谢。下面是我解决这个问题的代码

import java.io.*;
import java.util.*;

class Solution {
public static void main(String[] args) {

String x = "12:32 34:01 15:23 9:27 55:22 25:56";

String[] time = new String[6];
int[] mins = new int[6];
int[] secs = new int[6];
int hourTotal = 0;
int minTotal = 0;
int secTotal = 0;

Scanner scan = new Scanner(x);
scan.useDelimiter(" ");

int i = 0;
while(scan.hasNext() == true){

  time[i] = scan.next();
  Scanner scanz = new Scanner(time[i]);
  scanz.useDelimiter(":");

  int diff = 0;
  while(scanz.hasNext() == true){
    mins[i] = scanz.nextInt();
    secs[i] = scanz.nextInt();

    minTotal = minTotal + mins[i];
    secTotal = secTotal + secs[i]; 
  }
  while(secTotal >= 60){
    if(secTotal >= 60){
      secTotal = secTotal - 60;
      minTotal++;
    }
  }
  while(minTotal >= 60){
    if(minTotal >= 60){
      minTotal = minTotal - 60;
      hourTotal++;
    }
  }
}
i++;

System.out.print(hourTotal + ":" + minTotal + ":" + secTotal); 
  }
}

Answer 1

我会在这里使用split方法。我相信下面的代码将在O（n）时间内运行

class Time {
  public static void main(String[] args) {
    String x = "12:32 34:01 15:23 9:27 55:22 25:56";

    String[] time = x.split(" ");
    int hourTotal = 0;
    int minuteTotal = 0;
    int secondTotal = 0;

    String[] timeBreakdown;
    for (int i = 0; i < time.length ; i++) {
      timeBreakdown = time[i].split(":");
      minuteTotal = minuteTotal + Integer.parseInt(timeBreakdown[0]);
      secondTotal = secondTotal + Integer.parseInt(timeBreakdown[1]);

      if (secondTotal >= 60) {
        minuteTotal++;
        secondTotal = secondTotal - 60;
      }
      if (minuteTotal >= 60) {
        hourTotal++;
        minuteTotal = minuteTotal - 60;
      }
    }

    System.out.println(hourTotal + ":" + minuteTotal + ":" + secondTotal);
  }
}

Answer 2

public static void main(String[] args) {
    String x = "12:32 34:01 15:23 9:27 55:22 25:56";
    String[] minuteSecondPairs = x.split(" ");
    int totalMinute = Arrays.stream(minuteSecondPairs)
                            .mapToInt(pair -> Integer.parseInt(pair.split(":")[0]))
                            .sum();
    int totalSecond = Arrays.stream(minuteSecondPairs)
                            .mapToInt(pair -> Integer.parseInt(pair.split(":")[1]))
                            .sum();
    int remainingSecond = totalSecond % 60;
    totalMinute += (totalSecond - remainingSecond) / 60;
    System.out.println("Total hours: " + Math.floor(totalMinute/60) + " | Total minute: " + (totalMinute % 60) + " | Total second: " + remainingSecond);
}

这将在O（n）中运行