嵌套while循環的時間複雜度？

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）的運行