目錄
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)是
- 寫入(writing)物件到陣列中
- 從陣列中讀取(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?，我們該如何回答呢?
- 這個陣列最多能收藏幾個元素? (maximum size) => 容量(
capacity)- 目前這個陣列已經儲存了幾個元素? => 長度(
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)的概念，請先思考兩個問題
- 如何偵測到 1s 的新視窗的起點(starting point)?
- 如何偵測到 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; } }
