初级算法刷题系列三

旋转数组

• 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

---

• 解法1 使用临时数组

class Solution://使用临时数组 python实现
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums[:]=nums[len(nums)-k%len(nums):]+nums[:len(nums)-k%len(nums)]

复杂度分析
•	时间复杂度： O(n)，其中 n为数组的长度。
•	空间复杂度： O(n)。

• 解法2 多次反转

class Solution {//多次反转
    public void rotate(int[] nums, int k) {
    int len=nums.length;
    k%=len;
    reverse(nums,0,len-1);
    reverse(nums,0,k-1);
    reverse(nums,k,len-1);
    }
   public void reverse(int[] nums,int start,int end){
       while(start<end){
            int temp=nums[start];
            nums[start++]=nums[end];
            nums[end--]=temp;
       }    
    }
}
空间复杂度O(1)
时间复杂度O(n)

• 解法3 环形旋转

//环形旋转 把数组看作是环形的,每一个都向后移动k位
public void rotate(int[] nums, int k) {
        int len=nums.length;
        //保存被替代的数组元素
        int hold=nums[0];
        int index=0;
        /*如果数组长度是k的倍数，会出现原地打转的现象。定义一个数组，将访问过得数组元素保存起来
        如被访问过，则从下一个元素开始*/
        boolean visited[]=new boolean[len];
        for(int i=0;i<len;i++){
                index=(index+k)%len;
                if(visited[index]){//数组元素被访问过，再次访问的话会出现原地打转的现象
                        index=(index+1)%len;
                        hold=nums[index];
                        i--;
                }else{
                        //把当前值保存到下一个位置，保存之前把下个位置的值存到hold里
                        visited[index]=true;
                        int temp=nums[index];
                        nums[index] =hold;
                        hold=temp;
                }

        }
}

数组去重

• 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
• 解法1 set集合

public boolean containsDuplicate1(int[] nums) {
        //使用set集合不能有重复的特性
        Set<Integer> arr =new HashSet<>();
        for(int num:nums){
            arr.add(num);
            }
        return arr.size()!=nums.length;
        //时间复杂度：O(N)，其中 N为数组的长度。
        //空间复杂度：O(N)O，其中 N为数组的长度。
    }

• 解法2 sort排序

      public boolean containsDuplicate2(int[] nums) {
          //先用sort排序,查找重复元素
          Arrays.sort(nums);
          for(int i=1;i<nums.length;i++){
              if(nums[i-1]==nums[i]){
                  return true;
              }
          }
          return false;
      } //时间复杂度：O(NlogN)，其中 N为数组的长度。
      //空间复杂度：O(logN)，其中 N为数组的长度。
  }

  只出现一次的数字

• 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

  说明：算法具有线性时间复杂度。不使用额外空间来实现

public int singleNumber(int[] nums) {
        //异或运算,相同异或为0，不同异或为1.1^0=1,1^1=0,0^0=0,把所有数字异或一遍。
            // 时间复杂度O(n),其中n为数组长度，只需要对数组遍历一次
            //空间复杂度O(1)
            int reduce=0;
            for(int num:nums){
                reduce^=num;
        }
            return reduce;
    }

```