时间戳

首页 > 解决方案 > 用一个具体的例子来理解 Big-O

algorithm - 用一个具体的例子来理解 Big-O

问题描述

我正在研究一个相当简单的问题，以确保我理解这些概念。

问题是：存在一个包含 n 个元素的数组 A，可以是 RED、WHITE 或 BLUE。重新排列数组，使所有 WHITE 元素位于所有 BLUE 元素之前，并且所有 BLUE 元素位于所有 RED 元素之前。在 O(n) 时间和 O(1) 空间中构造一个算法。

据我了解，解决方案的伪代码是：

numW = numB = 0
for i = 0 to n:
    if ARRAY[i] == WHITE:
        numW++
    else if ARRAY[i] == BLUE:
        numB++

for i = 0 to n:
    if numW > 0:
        ARRAY[i] = WHITE
        numW--
    else if numB > 0:
        ARRAY[i] = BLUE
        numB--
    else:
        ARRAY[i] = RED

我相信它是 O(n)，因为它通过循环两次并且 O(2n) 在 O(n) 中。我相信空间是 O(1) 因为它不依赖于元素的总数，即每个元素都会有一个计数

我的理解正确吗？

标签： algorithmbig-oanalysispseudocode

解决方案

是的，您的解决方案在 O(1) 空间中的 O(n) 时间内运行。

下面是我的解决方案，它也在 O(n) 时间和 O(1) 空间中运行，但在我们引用对象时也可以工作，正如@kenneth 在评论中所建议的那样。

import java.util.Arrays;
import java.util.Random;
import static java.lang.System.out;

class Color{
    char c;
    Color(char c){
        this.c = c;
    }
}

public class Solution {

    private static void rearrangeColors(Color[] collection){
        int ptr = 0;   

        // move all whites to the left

        for(int i=0;i<collection.length;++i){
            if(collection[i].c == 'W'){
                swap(collection,ptr,i);
                ptr++;
            }
        }

        // move all blacks to the left after white       

        for(int i=ptr;i<collection.length;++i){
            if(collection[i].c == 'B'){
                swap(collection,ptr,i);
                ptr++;
            }
        }
    }

    private static void swap(Color[] collection,int ptr1,int ptr2){
        Color temp = collection[ptr1];
        collection[ptr1] = collection[ptr2];
        collection[ptr2] = temp;
    }

    private static void printColors(Color[] collection){
        for(int i=0;i<collection.length;++i){
            out.print(collection[i].c + ( i != collection.length - 1 ? "," : ""));
        }
        out.println();
    }

    public static void main(String[] args) {
        // generate a random collection of 'Color' objects
        Random r = new Random();
        int array_length = r.nextInt(20) + 1;// to add 1 if in case 0 gets generated 
        Color[] collection = new Color[array_length];
        char[] colors_domain = {'B','W','R'};

        for(int i=0;i<collection.length;++i){
            collection[i] = new Color(colors_domain[r.nextInt(3)]);
        }

        // print initial state
        printColors(collection);
        // rearrange them according to the criteria
        rearrangeColors(collection);
        // print final state
        printColors(collection);        
    }

}

推荐阅读