算法(初级):数组

2021年8月13日 19:23 阅读 1.01k 评论 0

1.两数之和

给定一个整数数组nums和一个整数目标值target,请你在该数组中找出 和为目标值 target的那两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。 示例 2:

输入:nums = [3,2,4], target = 6 输出:[1,2] 示例 3:

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

算法分析: 首先我们将两数之和改为知道 和 和 一个加数,求另一个加数是否存在的问题

这里使用了暴力破解

C

int* twoSum(int* nums, int numsSize, int target, int* returnSize){ 
    int *arr = NULL; // 定义空整形数组 
    for(int i=0;i<numsSize;i++){ // 遍历数字数组 
        for (int j=i+1;j<numsSize;j++){ // 遍历当前数之后的数组剩余部分 
            if (nums[i] + nums[j] == target){ // 若两数相加等于target 
                arr = (int*)malloc(sizeof(int)*2); // 分配两个整形空间 
                arr[0] = i;  
                arr[1] = j; 
                *returnSize = 2; // 数组长度为2 
                return arr;  
            } 
        }  
    } 
    return arr; 
} 

Python

class Solution: 
    def twoSum(self, nums: List[int], target: int) -> List[int]: 
        pos = {} 
        for index,num in enumerate(nums): 
            a_num = target - num 
            if a_num in pos: 
                return [pos[a_num],index] 
            pos[num] = index 
        return None 

2.搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法

示例 1:

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

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

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

算法分析:

首先我们需要手动排除当target小于等于数组第一个、大于数组最后一个的情况

if(target <= nums[0]){ 
    return 0; 
} 
if(target > nums[numsSize-1]){ 
    return numsSize; 
} 

排除后,算法就具有通用性了

我们遍历数组挨个与target对比,若当前数字大于等于target,返回其下标就可以了

int searchInsert(int* nums, int numsSize, int target){ 
    if(target <= nums[0]){ 
        return 0; 
    } 
    if(target > nums[numsSize-1]){ 
        return numsSize; 
    } 
    for (int j=1;j<numsSize;j++){ 
        if(nums[j] >= target){ 
            return j; 
        } 
    } 
    return 0; 
} 

PS:以上题目均来自LeetCode

最后修改于2021年8月28日 22:40
©允许规范转载

版权声明:如无特殊说明,文章均为本站原创,转载请注明出处

本文链接:https://www.yangyingqi.com/52.html

数组
微信
支付宝
登录后即可进行评论/回复