什么是线性查找
线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。
实现线性查找
下面我们使用线性查找在数组中查找某个元素
public class LinearSearch {public int search(int[] data, int target) {for (int i = 0, len = data.length; i < len; i++) {if (data[i] == target) return i;}return -1;}public static void main(String[] args) {int[] data = {1, 2, 3, 4, 5};LinearSearch ls = new LinearSearch();int res = ls.search(data, 10);System.out.println(res);}}
上面的代码使用线性查找在数组中查找一个元素，但是代码还值得优化
public class LinearSearch {
// 将构造函数声明成私有的防止用户创建LinearSearch类的对象
private LinearSearch() {}
private static int search(int[] data, int target) {
for (int i = 0, len = data.length; i < len; i++) {
if (data[i] == target) return i;
}
return -1;
}
public static void main(String[] args) {
int[] data = {1, 2, 3, 4, 5};
// LinearSearch 类是一个动词，不应该用创建对象的方式使用
int res = LinearSearch.search(data, 4);
System.out.println(res);
}
}
使用泛型
上面的代码只能查找 int 型的，怎么兼容其他类型呢，我们可以使用泛型来解决这个问题，但是需要注意在 Java 中使用泛型：不可以是基本类型，只能是类对象
Java 中的基本类型包含以下几种：
boolean、byte、char、short、int、long、float、double
它们都有对应的包装类
Boolean、Byte、Character、Short、Integer、Long、Float、Double
public class LinearSearch {
// 将构造函数声明成私有的防止用户创建LinearSearch类的对象
private LinearSearch() {}
private static <E> int search(E[] data, E target) {
for (int i = 0, len = data.length; i < len; i++) {
// == 用于基本数据类型时判断的是值是否相等，== 比较的是变量(栈)内存中存放的对象的(堆)内存地址，用来判断两个对象的地址是否相同，即是否是指相同一个对象。比较的是真正意义上的指针操作。equals用来比较的是两个对象的内容是否相等，由于所有的类都是继承自java.lang.Object类的，所以适用于所有对象，如果没有对该方法进行覆盖的话，调用的仍然是Object类中的方法，而Object中的equals方法返回的却是==的判断。要想判断类对象的值是否相等需要使用 equals()，在 Java 中字符串是类对象，判断值是否相等也需要使用 equals()
if (data[i].equals(target)) return i;
}
return -1;
}
public static void main(String[] args) {
Integer[] data = {1, 2, 3, 4, 5};
// LinearSearch 类是一个动词，不应该用创建对象的方式使用
int res = LinearSearch.search(data, 4);
System.out.println(res);
}
}
==比较的是两个字符串的地址是否为相等（同一个地址），equals()方法比较的是两个字符串对象的内容是否相同（当然，若两个字符串引用同一个地址，使用equals()比较也返回true）。
String a = "1";
String b = "1";
System.out.println(a == b); // true
String c = new String("1");
String d = new String("1");
System.out.println(c == d); // false
使用自定义类测试我们的方法
如果我们想使用自己定义的类应该怎么办呢，这就需要我们自己来实现 equals() 方法。
// src/Student.java
public class Student {
private String name;
public Student(String name) {
this.name = name;
}
@Override
public boolean equals(Object student) {
if (this == student) return true;
if (student == null) return false;
if (this.getClass() != student.getClass()) return false;
Student tempStudent = (Student)student;
return this.name.equals(tempStudent.name);
}
}
上面我们实现了一个学生类，并且实现了 equals() 方法，下面我们来测试下
// src/LinearSearch.java
public class LinearSearch {
// 将构造函数声明成私有的防止用户创建LinearSearch类的对象
private LinearSearch() {}
private static <E> int search(E[] data, E target) {
for (int i = 0, len = data.length; i < len; i++) {
if (data[i].equals(target)) return i;
}
return -1;
}
public static void main(String[] args) {
Student[] students = {new Student("f"), new Student("e"), new Student("y")};
Student student = new Student("y");
int res = LinearSearch.search(students, student);
System.out.println(res);
}
}
循环不变量
概念
循环是构建程序时一种非常重要的逻辑方式。循环不变量简单来说就是在循环的过程中保持不变的性质。也就是在每一轮循环的开始的时候，都满足某些性质。
上面的这个例子，在循环开始的时候是满足一个条件的，也就是在 data[0, i) 的位置是没有找到目标的。循环体的任务就是维持循环不变量，在上面的例子中每轮循环中，循环体中的代码要不就满足判断直接返回 i ，要不就进入下一轮循环，在下一轮循环中依旧满足 data[0,i) 没有找到目标。
如果在我们写的代码中有循环时，一定要定义清除循环不变量，循环不变量可以帮助我们维护一个正确的循环。
在循环当中虽然变量的值是变化的，但是保持不变的这些性质就是循环不变量。
练习题
循环不变量的定义决定了在循环的开始、循环过程中、循环结束后的一些细节。
26.删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var removeDuplicates = function(nums) {
const len = nums.length;
if (len < 2) return len;
let j = 1;
// 循环不变量：nums[0...j)有序，且元素唯一
// j 表示下一个需要覆盖的元素下标
for (let i = 1; i < len; i++) {
if (nums[i] !== nums[j-1]) {
nums[j] = nums[i]
j++;
}
}
return j;
};
var removeDuplicates = function(nums) {
const len = nums.length;
if (len < 2) return len;
let j = 0;
// 循环不变量：nums[0...j]有序，且元素唯一
// j 表示上一个赋值的元素下标
for (let i = 1; i < len; i++) {
if (nums[i] !== nums[j]) {
j++;
nums[j] = nums[i]
}
}
return j + 1;
};
283.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var moveZeroes = function (nums) {
const len = nums.length;
if (len <= 0) return nums;
let j = 0;
// 循环不变量：nums[0...j) !=0, nums[j...i) = 0
// j 指向下一个要赋值的元素位置
for (let i = 0; i < len; i++) {
if (nums[i] != 0) {
nums[j] = nums[i];
j++;
}
}
for (let i = j; i < len; i++) {
nums[i] = 0;
}
};
var moveZeroes = function (nums) {
const len = nums.length;
if (len <= 0) return nums;
let j = -1;
// 循环不变量：nums[0...j] !=0, nums(j...i) = 0
// j 指向上一个赋值的元素位置
for (let i = 0; i < len; i++) {
if (nums[i] != 0) {
j++;
nums[j] = nums[i];
}
}
for (let i = j + 1; i < len; i++) {
nums[i] = 0;
}
};
27.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var removeElement = function(nums, val) {
let len = nums.length;
let j = 0;
// 循环不变量：nums[0...j) !=val
// j 指向下一个要赋值的元素位置
for (let i = 0; i < len; i++) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
}
}
return j;
};
80.删除有序数组中的重复项II
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var removeDuplicates = function (nums) {
const len = nums.length;
if (len < 2) return len;
// 循环不变量：nums[0...j)有序，并且相同的元素最多保留 2 次
// j 指向下一个需要赋值元素位置
let j = 2;
for (let i = 2; i < len; i++) {
if (nums[i] !== nums[j - 2]) {
nums[j] = nums[i];
j++;
}
}
return j;
};
var removeDuplicates = function (nums) {
const len = nums.length;
if (len < 2) return len;
// 循环不变量：nums[0...j]有序，并且相同的元素最多保留 2 次
// j 指向上一个赋值元素的位置
let j = 1;
for (let i = 2; i < len; i++) {
if (nums[i] !== nums[j - 1]) {
j++;
nums[j] = nums[i];
}
}
return j + 1;
};
简单的复杂度分析
常见的时间复杂度
参考
若有收获，就点个赞吧
0 人点赞
