cpp-algo-cases/chapter_array_and_linkedlist/array.cpp

/**
 * File: array.cpp
 * Created Time: 2022-11-25
 * Author: krahets (krahets@163.com)
 */

#include "../utils/common.hpp"

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA> */
int randomAccess(int *nums, int size)
{ // *nums Ϊ<><CEAA><EFBFBD><EFBFBD><EFBFBD>׵<EFBFBD>ַ
    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD> [0, size) <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȡһ<C8A1><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    int randomIndex = rand() % size;
    // <20><>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA>
    int randomNum = nums[randomIndex]; // nums[randomIndex] <20>ȼ<EFBFBD><C8BC><EFBFBD> *(nums + randomIndex)
    return randomNum;
}

/* <20><>չ<EFBFBD><D5B9><EFBFBD>鳤<EFBFBD><E9B3A4> */
int *extend(int *nums, int size, int enlarge)
{
    // <20><>ʼ<EFBFBD><CABC>һ<EFBFBD><D2BB><EFBFBD><EFBFBD>չ<EFBFBD><D5B9><EFBFBD>Ⱥ<EFBFBD><C8BA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    int *res = new int[size + enlarge]; // <20><><EFBFBD><EFBFBD><EFBFBD>µ<EFBFBD><C2B5>ڴ<EFBFBD><DAB4>ռ<EFBFBD>
    // <20><>ԭ<EFBFBD><D4AD><EFBFBD><EFBFBD><EFBFBD>е<EFBFBD><D0B5><EFBFBD><EFBFBD><EFBFBD>Ԫ<EFBFBD>ظ<EFBFBD><D8B8>Ƶ<EFBFBD><C6B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    for (int i = 0; i < size; i++)
    {
        res[i] = nums[i];
    }
    // <20>ͷ<EFBFBD><CDB7>ڴ<EFBFBD>
    delete[] nums; // <20>ͷ<EFBFBD>ԭ<EFBFBD><D4AD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڴ<EFBFBD><DAB4>ռ<EFBFBD>
    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>չ<EFBFBD><D5B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    return res;
}

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> index <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA> num */
void insert(int *nums, int size, int num, int index)
{
    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD> index <20>Լ<EFBFBD>֮<EFBFBD><D6AE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƶ<EFBFBD>һλ
    for (int i = size - 1; i > index; i--)
    {
        nums[i] = nums[i - 1];
    }
    // <20><> num <20><><EFBFBD><EFBFBD> index <20><><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA>
    nums[index] = num;
}

/* ɾ<><C9BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD> index <20><><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA> */
void remove(int *nums, int size, int index)
{
    // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD> index ֮<><D6AE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA><EFBFBD><EFBFBD>ǰ<EFBFBD>ƶ<EFBFBD>һλ
    for (int i = index; i < size - 1; i++)
    {
        nums[i] = nums[i + 1];
    }
}

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
void traverse(int *nums, int size)
{
    int count = 0;
    // ͨ<><CDA8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
    for (int i = 0; i < size; i++)
    {
        count += nums[i];
    }
}

/* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>в<EFBFBD><D0B2><EFBFBD>ָ<EFBFBD><D6B8>Ԫ<EFBFBD><D4AA> */
int find(int *nums, int size, int target)
{
    for (int i = 0; i < size; i++)
    {
        if (nums[i] == target)
            return i;
    }
    return -1;
}

/* Driver Code */   // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
int main()
{
    /* <20><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
    int size = 5;
    int *arr = new int[size];
    cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD> arr = ";  // û<><C3BB>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӡ<EFBFBD><D3A1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ
    printArray(arr, size);

    int *nums = new int[size]{1, 3, 2, 5, 4};   // []{} <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD>ֳ<EFBFBD>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD>ʽ(<28><>ʼ<EFBFBD><CABC><EFBFBD>б<EFBFBD>)
    cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD> nums = ";
    printArray(nums, size);

    /* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
    int randomNum = randomAccess(nums, size);
    cout << "<EFBFBD><EFBFBD> nums <20>л<EFBFBD>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA> " << randomNum << endl;

    /* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>չ */
    int enlarge = 3;
    nums = extend(nums, size, enlarge);
    size += enlarge;
    cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>鳤<EFBFBD><EFBFBD><EFBFBD><EFBFBD>չ<EFBFBD><EFBFBD> 8 <20><><EFBFBD>õ<EFBFBD> nums = ";
    printArray(nums, size);

    /* <20><><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA> */
    insert(nums, size, 6, 3);
    cout << "<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> 3 <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> 6 <20><><EFBFBD>õ<EFBFBD> nums = ";
    printArray(nums, size);

    /* ɾ<><C9BE>Ԫ<EFBFBD><D4AA> */
    remove(nums, size, 2);
    cout << "ɾ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> 2 <20><><EFBFBD><EFBFBD>Ԫ<EFBFBD>أ<EFBFBD><D8A3>õ<EFBFBD> nums = ";
    printArray(nums, size);

    /* <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> */
    traverse(nums, size);

    /* <20><><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA> */
    int index = find(nums, size, 3);
    cout << "<EFBFBD><EFBFBD> nums <20>в<EFBFBD><D0B2><EFBFBD>Ԫ<EFBFBD><D4AA> 3 <20><><EFBFBD>õ<EFBFBD><C3B5><EFBFBD><EFBFBD><EFBFBD> = " << index << endl;

    // <20>ͷ<EFBFBD><CDB7>ڴ<EFBFBD>
    delete[] arr;
    delete[] nums;

    return 0;
}