listC++ Data Structure & Algorithm

Array Problem

สารบัญ

โจทย์ที่ 3: Single Number

โจทย์ https://leetcode.com/problems/single-number/description

อธิบายโจทย์แบบสั้นๆ มี Array nums มาให้ โดยตัวเลขใน array นี้จะซ้ำสองตัวเสมอ แต่จะมี “เพียงตัวเดียว” ที่จะไม่ซ้ำกัน จงนำตัวเลขนั้นออกมา

จากข้อมูลที่โจทย์ให้มา

Example 1:
Input: nums = [2,2,1]
Output: 1

Example 2:
Input: nums = [4,1,2,1,2]
Output: 4

Example 3:
Input: nums = [1]
Output: 1

เช่น จาก Testcase นี้

Example 1 input คือ [2,2,1] เราจะเจอว่า 1 คือตัวเลขตัวเดียวที่ไม่ซ้ำกัน ดังนั้น output = 1 เป็นคำตอบออกมา
Example 2 input คือ [4,1,2,1,2] เราจะเจอว่า 4 คือตัวเลขตัวเดียวที่ไม่ซ้ำกัน ดังนั้น output = 4 เป็นคำตอบออกมา

จากตัวอย่างนี้ Idea ที่เป็นไปได้แน่นอนคือ

ต้อง Loop ภายใน Array เพื่อหาที่ไม่ซ้ำออกมา
จาก LeetCode ใช้ Vector เช่นเดิม เพื่อรองรับ Array ที่มีหลายๆขนาดได้

Solution

class Solution {
public:
  int singleNumber(vector<int> &nums) {
    for (int i = 0; i < nums.size(); ++i) {
      bool isSingle = true;
      for (int j = 0; j < nums.size(); ++j) {
        if (i != j && nums[i] == nums[j]) {
          isSingle = false;
          break;
        }
      }
      if (isSingle) {
        return nums[i];
      }
    }
    // This line should theoretically never be reached if the input meets the
    // problem's conditions
    return -1; // Placeholder return value
  }
};

Core idea คือ

ใช้ singleNumber วน loop ซ้ำสองชั้นเพื่อเปรียบเทียบแต่ละ element ใน vector nums
function จะ return ตัวเลขที่ปรากฏเพียงครั้งเดียว หรือ return -1 ถ้าไม่มีตัวเลขที่ปรากฏเพียงครั้งเดียว การทำงานคือ
loop ผ่านแต่ละ element ใน vector nums โดยใช้ตัวแปร i
ภายใน for แต่ละรอบ วนซ้ำ อีกครั้ง ผ่านแต่ละ element ใน vector nums โดยใช้ตัวแปรวนซ้ำ j
เปรียบเทียบ nums[i] กับ nums[j]
- ถ้า i ไม่เท่ากับ j (ไม่ใช่ตำแหน่งเดียวกัน) และ nums[i] เท่ากับ nums[j]
- ตั้งค่า isSingle เป็น false (แปลว่ามีตัวเลขซ้ำกันเกิดขึ้น)
หลังจากออกจาก for ที่วนครบทุกตัว (ภายใน)
- ถ้า isSingle ยังเป็น true = return nums[i] ออกไปได้เลย (แปลว่าไม่มีตำเลขซ้ำเกิดขึ้น)

** จริงๆข้อนี้มี Solution ที่ดีกว่านี้ และใช้เพียง 1 loop อยู่

โจทย์ที่ 4: Search Insert Position

โจทย์ https://leetcode.com/problems/search-insert-position/description

อธิบายโจทย์แบบสั้นๆ มี Array ตัวเลขมาให้เรียงแล้วเรียบร้อย ให้หาตำแหน่งของตัวเลข target ที่ระบุมาว่าอยู่ index ที่เท่าไหร่ โดย มีกฎอยู่ว่า ถ้าหาตัวเลขนั้นไม่เจอ ให้ “บอก index ที่ต้องแทรกของตัวเลขนั้นออกมาแทน”

จากข้อมูลที่โจทย์ให้มา

cpp

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4

เช่น จาก Testcase นี้

Example 1 input คือ [1,3,5,6] และต้องการหาเลข 5 ซึ่งก็ชัดเจนตำแหน่งอยู่ index ที่ 2 Output ก็จะคืนเป็น index 2 ออกมา
Example 2 input คือ [1,3,5,6] และต้องการหาเลข 2 แต่เคสนี้ก็ชัดเจนเช่นกันว่าไม่มี และ index ที่มันจะต้องแทรกคือตำแหน่งระหว่าง 1 และ 3 ซึ่งก็คือ index 1 ที่จะทำให้ออกมาเป็น Array [1,2,3,5,6] ที่เรียงกันถูกต้องเหมือนเดิมออกมาได้

จากตัวอย่างนี้ Idea ที่เป็นไปได้แน่นอนคือ

ต้อง Loop ภายใน Array เพื่อหาตัวเลข
และถ้าไม่เจอตัวเลขต้องทำอะไรสักอย่างเพื่อระบุ Index ออกมาได้

คำใบ้ ไม่ต้องสร้าง Array ใหม่ออกมาจริงๆ

Solution

class Solution {
public:
  int searchInsert(vector<int> &nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
      // เช็ค target ว่าเจอ (target == nums[i]) สามารถคืน index ไปได้เลย
      // หรือ ถ้า element ตัวที่กำลังวน loop อยู่มีค่ามากกว่า (nums[i] > target) แปลว่านี่คือตำแหน่งที่สามารถแทรกเข้าไปได้ 
      // ดังนั้น เมื่อรวม logic กันก็จะสามารถใช้เป็น >= ได้
      if (nums[i] >= target) {
        return i;
      }
    }
    // ถ้าเกิดไม่เจอเลย แปลว่าตัวเลข target ใหญ่กว่าทุกตัวใน Array ให้คืนขนาดของ Array
    // ตำแหน่งสุดท้ายออกไปแทน
    return nums.size();
  }
};

arrow_backก่อนหน้าNumber Problem ถัดไปString Problemarrow_forward