目錄

1. Overview
2. Introduction
3. Inserting Items Into an Array
4. Deleting Items From an Array
5. Searching for Items in an Array
6. In-Place Operations
7. Conclusion
   
   

• LeetCode 官方連結: Explore - Arrays 101

Overview

前言

  Arrays 算是一種簡單的資料結構，在所有的程式語言中，皆有實作它。在這個 Explore Card 中，我們會利用 Arrays 來解決許多有趣的問題，這次的主題也是非常適合初學者，我們將會以 Java 作為 sample code 來說明觀念。


  讀完這個章節，我們將會理解以下觀念

• 什麼是 Array?
• Arrays 有哪些基本屬性(properties)?
• 如何實作 Arrays 的基本運作(basic operations)?
• 如何運用簡單的 Arrays 相關的程式設計技巧?

Introduction

Array - A DVD box?

  在這個章節中，我們將會介紹什麼是 Array，以及通常 Array 的用途是什麼? 接下來，我們將會用一個生活上的實際應用情境(e.g. 利用有組織的方法，來儲存許多的 DVDs)來說明，在 Java 中，如何建立、應用 Array 這個資料結構?

  我們想像一個情境，當我們要用一個紙箱來收納 DVDs 時，我們會需要考慮哪些事情?

• 新增一個 DVD 到紙箱裡
• 從紙箱裡刪除一個 DVD
• 這個紙箱能裝哪些類型的東西?

  對於每一個 DVD 應該會有些共同屬性(properties)，例如:

• 每一個 DVD 都會有一個塑膠外殼
• 每一個 DVD 都會有片名、卡司陣容、其它相關資訊
• 每一個 DVD 都會一樣大(same size)，並且紙箱的每一格只能放一片 DVD
• 圖例:
  

  此外，我們也會需要知道最多(maximum size)會有多少 DVDs 需要被收藏? 畢竟，我們應該不會想從 1990s 的 DVDs 開始收藏吧! 因此，當我們得知這個資訊的話，就能找到一個最適合的容量大小的紙箱來收藏這些 DVDs 了。而以上的情境說明，在程式設計的世界中，我們通常會用 Array 來儲存。

What Is an Array?

簡單來說，Array 是一個用來儲存物件(items)的集合(collection)。而這裡所謂的物件可以是 integers, strings, DVDs books ...等等，這些物件都是被連續(contiguous)存放在記憶體空間中的，因此要在 Array 中找到他們就會是很簡單的事情。

  承上一章節的情境說明，我們如何將收藏 DVDs 的故事，連接到程式設計的世界? 通常，我們不會把所有的 DVDs 散落在整個房間的各處吧! 我們通常會拿一個大紙箱或是書架來收藏它們。因此，當我們需要找到一個特定的 DVD 時，就不用在各個房間到處尋找了，可以在這個大紙箱或是書架上，輕易地找到它們。

Creating an Array

  在電腦的世界中，我們會需要指定這個 Array 最多能收藏多少個物件? 並且，這個最大容量是由我們(程式設計師)所決定的。此外，我們也必須同時指定好這個紙箱能收藏哪種類型的物件?

// The actual code for creating an Array to hold DVD's.
DVD[] dvdCollection = new DVD[15];

// A simple definition for a DVD.
public class DVD {
    public String name;
    public int releaseYear;
    public String director;

    public DVD(String name, int releaseYear, String director) {
        this.name = name;
        this.releaseYear = releaseYear;
        this.director = director;
    }

    public String toString() {
        return this.name + ", directed by " + this.director + ", released in " + this.releaseYear;
    }
}

  從以上的範例程式碼，我們可以討論以下幾件事情:
dvdCollection 這個 Array 最多只能收藏 15 個物件，並且陣列中的每一格都分別只能收藏一個物件，這些物件都是同一種類型(= DVD)。
為什麼我們不乾脆直接開一個擁有 1000000 格儲存空間的陣列呢? 因為實務上，當我們只是為了儲存 15 個 DVDs，就開設一個擁有 1000000 格儲存空間的陣列來收藏，是非常不值得，且過度浪費記憶體空間的行為!

Inserting Items Into an Array

Accessing Elements in Arrays

在 Array 的運作中，最原始的兩個操作(two most primitive operations)是

1. 寫入(writing)物件到陣列中
2. 從陣列中讀取(reading)物件
   而其它所有的運作都是基於這兩個最原始的操作而建立出來的。

Writing Items into an Array

  通常 Array 的索引都是從 0 開始計算的，也就是第一個元素所對應的索引是 0，第二個元素所對應的索引是 1 ...以此類推，索引的範圍會是 0 <= index <= N - 1，其中 N 是陣列長度。

/** 假設我們要將 The Avengers 這個 DVD 
新增到 dvdCollection 這個陣列中的第 8 格索引位置 **/

// Firstly, we need to actually create a DVD object for The Avengers.
DVD avengersDVD = new DVD("The Avengers", 2012, "Joss Whedon");

/** 讓我們再新增幾個 DVDs 物件到 dvdCollection 這個陣列中 **/

// Next, we'll put it into the 8th place of the Array. Remember, because we
// started numbering from 0, the index we want is 7.
dvdCollection[7] = avengersDVD;

DVD incrediblesDVD = new DVD("The Incredibles", 2004, "Brad Bird");
DVD findingDoryDVD = new DVD("Finding Dory", 2016, "Andrew Stanton");
DVD lionKingDVD = new DVD("The Lion King", 2019, "Jon Favreau");

// Put "The Incredibles" into the 4th place: index 3.
dvdCollection[3] = incrediblesDVD;

// Put "Finding Dory" into the 10th place: index 9.
dvdCollection[9] = findingDoryDVD;

// Put "The Lion King" into the 3rd place: index 2.
dvdCollection[2] = lionKingDVD;

/** 那麼，若我們對 dvdCollection 陣列的第 3 格索引位置新增一個 DVD 物件，會發生什麼事情呢? **/
DVD starWarsDVD = new DVD("Star Wars", 1977, "George Lucas");
dvdCollection[3] = starWarsDVD;  // 若陣列中該索引位置已經存在值，會被覆寫(overwritten)

Reading Items from an Array

/** 讓我們來檢視 dvdCollection 這個陣列中，指定索引位置的值 **/

// Print out what's in indexes 7, 10, and 3.
System.out.println(dvdCollection[7]);
System.out.println(dvdCollection[10]);
System.out.println(dvdCollection[3]);

// Will print:

// The Avengers, directed by Joss Whedon, released in 2012
// null
// Star Wars, directed by George Lucas, released in 1977

  這邊要注意的是，在 C 語言中，若在陣列中該格索引位置的值不存在的話，可能會回傳隨機值(completely random data); 而在 Java 語言中，會回傳該陣列在宣告時所指定的元素類型，例如: 物件[]，回傳 null; 其它原始型別(primitive types)會回傳該原始型別所對應的初始值，像是 int[]，回傳 0; float[]，回傳 0.0，bool[]，回傳 false。

Writing Items into an Array with a Loop

  通常，我們會利用迴圈(loop)來遍歷新增元素到陣列中。

/** 利用 for loop 來新增元素到陣列中 **/
int[] squareNumbers = new int[10];

// Go through each of the Array indexes, from 0 to 9.
for (int i = 0; i < 10; i++) {
    // We need to be careful with the 0-indexing. The next square number
    // is given by (i + 1) * (i + 1).
    // Calculate it and insert it into the Array at index i.
    int square = (i + 1) * (i + 1);
    squareNumbers[i] = square;
}

  另外，當我們只是想要遍歷陣列中的各個元素，而不會用到索引(index)時，可以採用 for each loop，這樣的程式碼會更精簡。 記住! 越簡單(simple)、越優雅(elegant)的程式碼，就是好的程式碼(good code)。

/** 利用 for each loop 來遍歷陣列中的各個元素 **/
// For each VALUE in the Array.
for (int square : squareNumbers) {
    // Print the current value of square.
    System.out.println(square);
}
// Prints exactly the same as the previous example.

Reading Items from an Array with a Loop

  通常，我們也會用迴圈(loop)來遍歷印出陣列中的各個元素。

// Go through each of the Array indexes, from 0 to 9.
for (int i = 0; i < 10; i++) {
    // Access and print what's at the i'th index.
    System.out.println(squareNumbers[i]);
}

// Will print:
// 1
// 4
// 9
// 16
// 25
// 36
// 49
// 64
// 81
// 100

Array Capacity VS Length

前情提要: 若有人問我們 how long the DVD Array is?，我們該如何回答呢?

1. 這個陣列最多能收藏幾個元素? (maximum size) => 容量( capacity )
2. 目前這個陣列已經儲存了幾個元素? => 長度( length )
   其實以上兩種回答都是可以接受的，但兩者背後分別代表兩種意思。我們必須清楚地區別兩者的不同，並且正確地使用它們。

Array Capacity

// Arrays Capacity
DVD[] array = new DVD[6] // fixed size
array[0], array[1], array[2], array[3], array[4], and array[5]

int capacity = array.length;
System.out.println(array[0]); // null
System.out.println(array[5]); // null
System.out.println(array[100]); // 會拋出 `ArrayIndexOutOfBoundsException` 錯誤
System.out.println("The Array has a capacity of " + capacity); // The Array has a capacity of 6

Array Length

  而真正的 Array Length，也就是按照定義來說，表示目前陣列中已經儲存了幾個元素? 我們(程式設計師)必須自己負責追蹤(track)，並且電腦不會自動地提醒我們當我們覆寫(overwrite)某一個元素的值，或是我們跳過某幾格，而留下空隙(leave a gap)在陣列中。

  實務上，我們通常會用 Arrays.length 語法，來進行追蹤 Array 中目前已經儲存了幾個元素?

// Create a new array with a capacity of 6.
int[] array = new int[6];

// Current length is 0, because it has 0 elements.
int length = 0;

// Add 3 items into it.
for (int i = 0; i < 3; i++) {
    array[i] = i * i;
    // Each time we add an element, the length goes up by one.
    length++;
}

System.out.println("The Array has a capacity of " + array.length); // The Array has a capacity of 6
System.out.println("The Array has a length of " + length); // The Array has a length of 3

Handling Array Parameters

  在 LeetCode 的題目中，常常會看到題目會提供一個 Array，但沒有提供該陣列的 Capacity 或 Length 參數，這表示什麼呢? 讓我們先看看以下的範例題目:

Given a binary array, find the maximum number of consecutive 1s in this array.
說明: 當題目只有給 Array 參數，而沒有給 Capacity 或 Length 參數時，我們可以直接假設 length == capacity，也就是說該 Array 目前是空的(empty)，並擁有所有的 capacity 空間可以用來儲存元素。因此，我們可以善用 Arrays.length 語法，來完成這個題目。

  需要注意的是，Array 的索引是從 0 開始計算的(0-indexed)。因此，capacity/length 是表示陣列中有多少個元素，而不是最高的索引(highest index)，因為最高的索引會是 Arrays.length - 1。綜上所述，我們可以利用以下的範例程式碼來遍歷整個陣列中的各個元素。

/** sample template code **/

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        // Hint: Initialise and declare a variable here to 
        // keep track of how many 1's you've seen in a row.
        for (int i = 0; i < nums.length; i++) {
            // Do something with element nums[i].
        }
    }
}

  以上就是關於 Array 基本操作的介紹，讓我們來練習一些相關的題目吧!

練習題目(Introduction)

#485 Max Consecutive Ones

• 題目說明:
• 提示 1: 利用滑動視窗(sliding window)的概念，請先思考兩個問題
  • 1. 如何偵測到 1s 的新視窗的起點(starting point)?
  • 1. 如何偵測到 1s 的新視窗的終點(ending point)?
  • 只要掌握以上兩個資訊，剩下的就只是找出最長的 1s 視窗，並回傳之
• 圖解:
  

• 解答:
  

  • /**
     * One pass
     * @note `N` is the number of elements in the array.
     * Time Complexity: O(N).
     * Space Complexity: O(1). We do not use any extra space.
     */
    class Solution {
        public int findMaxConsecutiveOnes(int[] nums) {
            // 宣告一個要用來回傳的 "連續最長 1s" 的長度
            int maxConsecutiveOnes = 0;
            // 宣告一個臨時計數器(for 1s)
            int tempOnes = 0;
            for (int num: nums) {
                // 若遇到 1
                if (num == 1) {
                    // 將臨時計數器 +1
                    tempOnes++;
                    // 比較當前的 Math.max(連續最長 1s 的長度, 臨時計數器)的值，回傳較大值者
                    maxConsecutiveOnes = Math.max(maxConsecutiveOnes, tempOnes);
                // 反之，若遇到 0
                } else {
                    // 比較當前的 Math.max(連續最長 1s 的長度, 臨時計數器)的值，回傳較大值者
                    maxConsecutiveOnes = Math.max(maxConsecutiveOnes, tempOnes);
                    // 將臨時計數器 0
                    tempOnes = 0;
                }
            }
    
            return maxConsecutiveOnes;
        }
    }
    

#1295 Find Numbers with Even Number of Digits

#977 Squares of a Sorted Array

Deleting Items From an Array

Searching for Items in an Array

In-Place Operations

Conclusion