网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

1. 数组

2021/5/28 14:03:10 人评论

数组 1. 概念: 数组是在内存中存储相同数据类型的连续的空间 声明一个数组就是在内存空间中划出一串连续的空间 数组名 代表的是连续空间的首地址 通过首地址可以依次访问数组所有元素 元素在数组中的排序叫做下标 从零开始 2. 区分元素和索引(下标&a…

数组

1. 概念:

数组是在内存中存储相同数据类型的连续的空间

声明一个数组就是在内存空间中划出一串连续的空间

数组名 代表的是连续空间的首地址

通过首地址可以依次访问数组所有元素

元素在数组中的排序叫做下标 从零开始

2. 区分元素和索引(下标)

举例: 数组 [1,22,3,44,5]

数组的元素是数组内部具体的值,1,22,3,44,5

下标(索引)从零开始, 0,1,2,3,4,

3. 访问(Access)和搜索(Search)

**访问 **是 通过下标是找这个元素的值

**搜索 **是 直接查找元素

4. 数组的四种方法

1. 访问(Access):O(1)

可以通过数学公式找到

举例:

int a[1,2,3]

访问每个元素,假如数组内存地址是10,a[1]的地址为10+1*4=14,其中4为int占用4个字节

2. 搜索(Search):O(N)

从头到尾遍历

最差为遍历到最后找到想找的元素

3. 插入(Insert): O(N)

将 要插入的元素 的 后面的元素 都往后移

最差的情况是在第一个元素后面插入,那么之后的元素都往后移

如果插入时后移空间不够,则需要开辟新的内存空间来执行操作

4. 删除(Delete):O(N)

删除一个元素时,其余元素前移,因为数组的空间是连续的

最差情况是,前面删除一个元素,后面的都往前移

对比两个数组也就是对比以上内容

5. 特点:

读 √

写 ×

6. 常用操作

1. 创建数组

四种常用方法:

  1. int[] arr = {1,2,3};
  2. int[] arr = new int[]{1,2,3};

常用:

  1. int[] arr = new int[3]; 当不知道数组应该放多少个元素,用这个
  2. ArrayList<Integer> arr =new ArrayList<>(); 不需要指定长度和元素,用这个

2. 添加元素

在这里插入图片描述

使用的是ArrayList的方式

O(1)是插在尾端,O(N)是插在中间

3. 访问元素

在这里插入图片描述

c[1]是普通方法,

arr.get(1)是ArrayList的方法

4. 修改(更新)元素

在这里插入图片描述

c[1]是普通方法,

arr.set(1,11)是ArrayList的方法

5. 删除元素

在这里插入图片描述

使用的是ArrayList的方式

6. 数组的长度

在这里插入图片描述

这两个方法时间复杂度是O(1),每次操作,内部有个count会帮助计算

c.length是普通方法,

arr.size()是ArrayList的方法

7. 遍历元素

在这里插入图片描述

这两个方法时间复杂度是O(N)

c.length是普通方法,

arr.size()是ArrayList的方法

8. 查找元素

在这里插入图片描述

普通方式,一个个遍历,然后看有没有要找的那个元素

ArrayList方式,用contains()方法

9. 数组排序(内置排序法)

用的是自带的排序方法,并非自己写的

在这里插入图片描述

普通和ArrayList都有sort()方法

从大到小排序:

​ 普通:Arrays.sort(T[],Collections.reverseOrde()); 此题中,T[]Integer[] c,要传对象方式

​ ArrayList:Collections.sort(arr, Collections.reverseOrder( ));

Leetcode

485.最大连续1的个数

1.先判断数组长度是否为0或者数组为空

2.定义一个计数器count,和存放结果的result

3.遍历数组,如果元素为1,计数器+1

如果不为1,result=result和count的最大值,同时计数器置为0

4.遍历完毕后,返回=result和count的最大值

代码如下:

public class array {
    public int findMaxConsecutiveOnes(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return 0;
        }
        int count = 0;
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                count++;
            } else {
                result = Math.max(result, count);
                count = 0;
            }
        }
        return Math.max(result, count);
    }
}

283.移动零

方法一:

两次遍历
我们创建两个指针i和index,第一次遍历的时候指针index用来记录当前有多少非0元素。即遍历的时候每遇到一个非0元素就将其往数组左边挪,第一次遍历完后,j指针的下标就指向了最后一个非0元素下标。
第二次遍历的时候,起始位置就从index开始到结束,将剩下的这段区域内的元素全部置为0。

public class zero {
    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index] = nums[i];
                index++;
            }
        }
        for (int i = index; i < nums.length; i++) {
            nums[i] = 0;
        }
}

动画演示 283.移动零 - 移动零 - 力扣(LeetCode) (leetcode-cn.com)

方法二:

参考了快速排序的思想,快速排序首先要确定一个待分割的元素做中间点x,然后把所有小于等于x的元素放到x的左边,大于x的元素放到其右边。
这里我们可以用0当做这个中间点,把不等于0(注意题目没说不能有负数)的放到中间点的左边,等于0的放到其右边。
这的中间点就是0本身,所以实现起来比快速排序简单很多,我们使用两个指针i和j,只要nums[i]!=0,我们就交换nums[i]nums[j]

package qi.array;

/**
 * 移动0
 */
public class zero {
  public void moveZeroes(int[] nums) {
      if(nums==null) {
          return;
      }
      //两个指针i和j
      int j = 0;
      for(int i=0;i<nums.length;i++) {
          //当前元素!=0,就把其交换到左边,等于0的交换到右边
          if(nums[i]!=0) {
              int tmp = nums[i];
              nums[i] = nums[j];
              nums[j++] = tmp;
          }
       }
      
}

27.移除元素

方法一:

左右指针

  1. 判断

  2. 定义两个指针

  3. 在 左< 右 的时候

    如果左 != 值,左指针右移,

    如果 右 = 值,右指针左移

  4. 交换左右指针上的的元素

  5. 返回,如果 左指针或者右指针(因为最后两个指针会指向同一个位置) 上的元素等于val,返回当前指针,否则返回指针加一

public int removeElement(int[] nums, int val) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int l = 0;
    int r = nums.length - 1;
    while (l < r) {
        while (l < r && nums[l] != val) {
            l++;
        }
        while (l < r && nums[r] == val) {
            r--;
        }
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;

    }

    return nums[l] == val ? l : l + 1;
}

方法二:

快慢指针

把不为val的放在j的位置上

最后返回j的下标

public int removeElement(int[] nums, int val) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[j] = nums[i];
            j++;
        }
    }
    return j;
}

方法三:

暴力破解法

将要移除的元素的后面的所有元素往前移

public int removeElement(int[] nums, int val) {
    int size = nums.length;
    for (int i = 0; i < size; i++) {
        if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
            for (int j = i + 1; j < size; j++) {
                nums[j - 1] = nums[j];
            }
            i--; // 因为下表i以后的数值都向前移动了一位,所以i也向前移动一位
            size--; // 此时数组的大小-1
        }
    }
    return size;
}

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?