数组和字符串

chordxx / 2023-04-29 / 原文

数组操作

读取数组中的元素，是通过访问索引的方式来读取的，一般从0位置开始。

对于数组，计算机在内存中为其申请一段连续的空间，且会记下索引为0处的内存地址。主要的四种操作为：读取，查找，插入和删除元素。

1.寻找数组的中心索引：

给定整数数组nums，计算数组的中心下标（其左侧所有元素相加之和等于右侧元素相加之和，注意这里不包括索引处元素本身）。如果存在多个中心下标，返回最左边的一个，如果不存在中心下标，则返回-1。

示例：

输入：nums = [1, 7, 3, 6, 5, 6]

输出：3

解释：中心下标是 3 。

左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，

右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11.

输入：nums = [1, 2, 3] 输出：-1

输入：nums = [2, 1, -1] 输出：0

思路：先求出数组总和，然后从左侧元素开始求部分和，通过减法实现与剩下元素之和比较。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int i,sum=0,left_sum=0;
        for(i=0;i<nums.size();i++) sum+=nums[i];
        for(i=0;i<nums.size();i++){
            if(left_sum==sum-left_sum-nums[i]) return i;
            left_sum+=nums[i];
        }
        return -1;
    }
};

2.搜索插入位置：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 :

输入: nums = [1,3,5,6], target = 5
输出: 2

输入: nums = [1,3,5,6], target = 2
输出: 1

输入: nums = [1,3,5,6], target = 7
输出: 4

思路：由于这里要求使用时间复杂度 O(log n)，则联想到用二分法实现2^n的变化。

设置left，right，mid分别表示最小，最大和中间位置的索引。不断比较插入值和mid值的大小，从而改变left和right。

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4         int i=1,mid=0,left=0,right=nums.size()-1;
 5         mid=(left+right)/2;
 6 
 7         //首先排除最小和最大的可能，注意最小也只能是0，但是最大下标需要考虑是否+1
 8         if(target<=nums[0]) return 0;
 9         if(target==nums[right]) return nums.size()-1;
10         if(target>nums[right]) return nums.size();
11 
12         //由于只能最大下标为空，这里考虑right，但是因为right不可能为空，因此需要一个break能结束循环
13         while(nums[right]!='\0'){
14             if(target==nums[mid]) return mid;
15             if(mid==left) break; //因为是除法运算，所以mid下标只会和较小的left相等，不考虑right
16             if(target<nums[mid]){
17                 right=mid; mid=(left+right)/2;
18             }
19             if(target>nums[mid]){
20                 left=mid; mid=(left+right)/2;
21             }
22         }
23         return mid+1; //下标mid=left时说明值偏大，因此需要结果+1
24     }
25 };