数据结构之数组

一.从排序数组中删除重复项

1.就是进行比较，如果和前面那一个相等，就进行删除咯

def deleteArray(arr):
    before=0
    back=1
    while back<len(arr):
        if arr[before]==arr[back]:
            arr.pop(back)
        else:
            before=before+1
            back=back+1
    return arr

二.旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。旋转数组

如果是在旋转数组中查找最大元素，采用二分法即可，因为两边都是有序的

def rotate_arr1(arr,k):
    if not arr:
        return arr
    length=len(arr)
    k%=len(arr)
    arr[:length-k],arr[length-k:]=arr[k:],arr[:k]
    return arr
arr=[1,2,3,4,5,6,7]
print(rotate_arr1(arr,10))

三.存在重复

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数应该返回 true。如果每个元素都不相同，则返回 false。

思想一：判断是否为重复，可以用dict统计次数

思想二：如果不用特殊结构(字典)呢？排序，然后再判定，时间复杂度有点高

有想法的，可以说一说，嘿嘿

#思路2
def isDuplicate1(arr):
    if not arr:
        return False
    arr.sort()
    length=len(arr)
    for i in range(1,length):
        if arr[i-1]==arr[i]:
            return True
arr1=[1,2,3,4,4,5]
print(isDuplicate1(arr1))
#思路1
def isDuplicate2(arr):
    dict={}
    for i in arr:
        if i not in dict:
            dict[i]=1
        else:
            dict[i]+=1
    for i in dict.values():
        if i>1:
            return True
    return False
arr2=[1,2,3,4,5]
print(isDuplicate2(arr2))

四.只出现了一次的数字

方法1：这个很简单,用两个set就可以解决

一个统计重复的元素，然后把重复的元素删除即可

方法2：不行就排序，然后再统计

def Duplicate3(arr):
    if not arr:
        return arr
    dict={}
    list=[]
    for i in arr:
        if i not in dict:
            dict[i]=1
        else:
            dict[i]+=1
    for key,item in dict.items():
        if dict[key]==1:
            list.append(key)
    return list
arr=[1,2,3,3,4,5,6,7]
print(Duplicate3(arr))

如果只存在一个一个重复的元素，其它元素的个数都为偶数，可以采用异或进行获取

数组中只出现一次的数字，在这里面它采用了另类的划分手法，很强势

五.两个数组的交集

两个数组的交集，其实可以使用zip来进行两个列表的遍历(这个方法不可靠，局限性太大)

还是使用遍历吧

def intersection2(arr1,arr2):
    if not arr1 or not arr2:
        return
    arr1.sort()
    arr2.sort()
    count1=0
    count2=0
    list=[]
    while count1<len(arr1) and count2<len(arr2):
        if arr1[count1]==arr2[count2]:
            list.append(arr1[count1])
            count1+=1
            count2+=1
        elif arr1[count1]<arr2[count2]:
            count1+=1
        else:
            count2+=1
    return list

或者使用字典进行统计

def intersect3(nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1Dic = {}
        numsList = []
        for i in nums1:
            if nums1Dic.get(i):
                nums1Dic[i] += 1
            else:
                nums1Dic[i] = 1
        for i in nums2:
            if nums1Dic.get(i):
                numsList.append(i)
                nums1Dic[i] -= 1
        return numsList

六.加一

个位加1，考虑一下进位的问题就行了

给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

def addOne(arr):
    #只是加一
    extra=0
    one=1
    arr=arr[::-1]#因为是加最后一位，所以反转
    for index,item in enumerate(arr):
        if item+one+extra==10:
            extra=1
            one=0
            arr[index]=0
        else:
            arr[index]=item+one+extra
            return arr[::-1]
    arr.append(1)#如果所有都进位了就加1
    return arr[::-1]

七.移动零

给定一个数组 nums, 编写一个函数将所有 0 移动到它的末尾，同时保持非零元素的相对顺序。

例如， 定义 nums = [0, 1, 0, 3, 12]，调用函数之后， nums 应为 [1, 3, 12, 0, 0]。

注意事项

必须在原数组上操作，不要为一个新数组分配额外空间。

尽量减少操作总数。

def move_zero(arr):
    if not arr:
        return arr
    j=0
    for i in range(len(arr)):#i是重零开始的
        if arr[i]!=0:
            arr[j],arr[i]=arr[i],arr[j]
            j+=1
    return arr

 

八.两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。(所有的)

class Solution:
    def twoSum(self,nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #用len()方法取得nums列表长度
        n = len(nums)
        #x从0到n取值（不包括n）
        for x in range(n):
            a = target - nums[x]
            #用in关键字查询nums列表中是否有a
            if a in nums:
                #用index函数取得a的值在nums列表中的索引
                y = nums.index(a)
                #假如x=y,那么就跳过,否则返回x,y
                if x == y:
                    continue
                else:
                    return x,y
            else :
                continue

九.n数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的数组合。三数之和是否为0

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        nums.sort()#排序
        res =[]
        i = 0
        for i in range(len(nums)):
            if i == 0 or nums[i]>nums[i-1]:
                l = i+1
                r = len(nums)-1
                while l < r:
                    s = nums[i] + nums[l] +nums[r]
                    if s ==0:
                        res.append([nums[i],nums[l],nums[r]])
                        l +=1
                        r -=1
                        while l < r and nums[l] == nums[l-1]:#避免相同值
                            l += 1
                        while r > l and nums[r] == nums[r+1]:
                            r -= 1
                    elif s>0:
                        r -=1
                    else :
                        l +=1
        return res
num=[-1,0,1,2,-1,-4]
s=Solution()
print(s.threeSum(num))

十.与排序思想相结合的问题

应用比较广泛的几种排序思想主要有：快速排序（荷兰国旗问题、三路快排），计数排序（适用于数据比较少的状况，比如荷兰国旗问题）、归并排序（引申出多路归并问题，原来的归并为二路归并）

十一.滑动窗口技术

滑动窗口思路： 
解决部分数组问题时，设置两个索引下标i,j，i为左边界，j为右边界，逐渐遍历整个数组，i和j组成的子数组形成长度变化的滑动窗口，直至i遍历完整个数组。

题目1:给定一个数组和一个滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组 {2，3，4，6，2，5，1} 及滑动窗口的大小 3，那么一定存在 6 个滑动窗口，它们的最大值分别为 {4，6，6，6，5}。

def slide_window2(arr,k):#这是求滑动窗口中最大的数
    res=[]
    i=0
    while(i<len(arr)-k+1):
        res.append(max(arr[i:i+k]))
        i+=1
    return res

题目2：Leetcode 209：Minimum Size Subarray Sum 
给定一个整型数组和一个数字s，找到数组中最短的一个连续子数组，使得连续子数组的数字和sum>=s，返回这个最短的连续子数组的长度值

这里面的k是不定的，那我们该怎么样去定k呢，就是从头遍历，直下一个，统计

def min_subarr(nums,s):
    if not nums:
        return
    if sum(nums[:])<s:
        return 
    l=0
    r=-1
    sums=0
    res=len(nums)+1
    while l<len(nums):
        if sums<s and r<len(nums)-1:
            r+=1
            sums+=nums[r]
        else:
            sums-=nums[l]
            l+=1
        if sums>s:
            res=min(res,r-l+1)
    return res

题目3： Leetcode 3：Longest Substring Without Repeating Characters 
在一个字符串中寻找没有重复字母的最长子串，返回长度值

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 滑动窗口，右边界右移，直到找到有重复字符，记录长度，然后将左边界右移到重复的数组+1位置，再继续右移右边界，直到找到新的重复字符
        # 时间复杂度O(n)，空间复杂度O(1)
        freq = [0 for _ in range(256)]  # 用于记录每个字符串当前出现频率，索引为每个字符串对应的ASCII码
        l = 0
        r = -1  # nums[l...r]为滑动窗口
        res = 0  # 初始化为最小
        while l < len(s):
            # 当右边界下一个位置s[r+1]的频率为0时才右移，否则有重复字符，就右移左边界直到没有重复字符
            if (r < len(s)-1) and freq[ord(s[r+1])] == 0:
                r += 1
                freq[ord(s[r])] += 1
            else:
                freq[ord(s[l])] -= 1
                l += 1
            # 每次循环中滑动窗口内永远不会有重复字符，所以每次都可以做比较，最终res为最大值
            res = max(res, r-l+1)
        return res