我的问题很简单，从下面的代码来看，您如何实现一种算法，在找到中间值后搜索相同出现的项目？假设数据已排序。
非常感谢你们帮助我根据下面的代码实现。 我有一些方法，例如添加额外的函数，例如指数搜索，但我担心这会破坏算法的时间复杂度。
我希望你们实现一个算法，查找多个相同的项目并计算它们的出现次数，并且它将允许下面代码的时间复杂度保持为 O(LOG N)
private boolean binarySearchComparator(TYPE key) {
int low = 0;
int high = count - 1;
while (low <= high) {
int mid = (low + high) / 2;
TYPE midVal = list[mid];
int cmp = comparator.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return true;
}
}
我的完整代码请看一下。
排序列表界面
public interface SortedListInterface <TYPE extends Comparable<TYPE>> {
public boolean add(TYPE element);
public TYPE get(int index);
public int search(TYPE element);
public TYPE remove(int index);
public void clear();
public int getLength();
public boolean isEmpty();
public boolean isFull();
}
SearchComparator 类
public class MobileSearch implements Comparator<Student>{
private String type;
public void setType(String type) {
this.type = type;
}
public String getType() {
return type;
}
@Override
public int compare(Student student1, Student student2) {
int result = 0;
if(this.type.equals("mobile")){
result = student1.getMobileNo().compareTo(student2.getMobileNo());
System.out.print(result+"mobile");
}
else if(this.type.equals("name")){
result = student1.getName().getFullName().compareTo(student2.getName().getFullName());
System.out.println(result+"name");
}
else if(this.type.equals("group")){
result = student1.getGroup().compareTo(student2.getGroup());
System.out.print(result+"group");
}
return result;
}
}
SortedArrayList 实现
public class SortedArrayList<TYPE extends Comparable<TYPE>> implements SortedListInterface<TYPE>{
//Data Types
private TYPE[] list;
private int length;
private static final int SIZE = 10;
private Comparator<? super TYPE> comparator;
private int count;
@SuppressWarnings("unchecked")
public SortedArrayList(Comparator<? super TYPE> c) {
comparator = c;
list = (TYPE[]) new Comparable[SIZE]; // No way to verify that 'list' only contains instances of 'T'.
/* NOTE: Following is not allowed.
list = new T[SIZE]; // Cannot create a generic array of T
*/
}
// Constructors
public SortedArrayList() {
this(SIZE);
}
public SortedArrayList(int size) {
length = 0;
list = (TYPE[]) new Comparable[SIZE]; // an array of instances of a class implementing Comparable interface and able to use compareto method but its overidden instead
}
// Setter & Getters
@Override
public int getLength() {
return length;
}
@Override
public boolean isEmpty() {
return length == 0;
}
@Override
public boolean isFull() {
return false;
}
@Override
public void clear() {
length = 0;
}
// Array Expansion
private boolean isArrayFull() {
return length == list.length;
}
private void expandArray() {
TYPE[] oldList = list;
int oldSize = oldList.length;
list = (TYPE[]) new Object[2 * oldSize];
for (int i = 0; i < oldSize; i++) // copy old array elements into new array elements
list[i] = oldList[i];
}
// ADT METHODs
// Add New Elements Function
@Override
// public boolean add(TYPE element) {
// int i = 0;
//
// while (i < length && element.compareTo(list[i]) > 0) // return 0 with equal , return more than 1 if element larger than list[i] , return -1 if less
// {
// i++;
// }
//
// makeRoom(i + 1);
// list[i] = element;
// length++;
// return true;
// }
public boolean add(TYPE element) {
boolean result = false;
if (count == 0) {
list[0] = element;
count = 1;
result = true;
}
else {
if (!isFull()) {
int i = 0;
while (list[i] != null) {
if (element.compareTo(list[i]) < 0) {
break;
}
i++;
}
if (list[i] != null) {
for (int j = count - 1; j >= i; j--) {
list[j + 1] = list[j];
}
}
list[i] = element;
count++;
result = true;
}
}
return result;
}
private void makeRoom(int index) { // accepts given index
int newIndex = index - 1;
int lastIndex = length - 1;
for (int i = lastIndex; i >= newIndex; i--)
list[i + 1] = list[i];
}
//Remove Elements Function
@Override
public TYPE remove(int index) { // accepts given index
TYPE result = null;
if ( index >= 1 && index <= length ) {
result = list[index - 1];
if (index < length)
removeGap(index);
length--;
}
return result;
}
private void removeGap(int index) { // accepts given index and remove the gap where the element its removed
int removedIndex = index - 1;
int lastIndex = length - 1;
for (int i = removedIndex; i < lastIndex; i++)
list[i] = list[i + 1]; // shifts elements back to remove the gap
}
// Get Element
@Override
public TYPE get(int index) { // accepts given index and return the object
TYPE object = null;
if ( index >= 1 && index <= length)
object = list[index - 1];
return object;
}
// Search Algorithms
@Override
// public boolean search(TYPE element) {
// boolean found = false;
//
// int lo = 0;
// int hi = count - 1;
//
// while (lo <= hi) {
// int mid = (lo + hi) / 2;
// if (list[mid].compareTo(element) < 0) {
// lo = mid + 1;
// }
// else if (list[mid].compareTo(element) > 0) {
// hi = mid - 1;
// }
// else if (list[mid].compareTo(element) == 0) {
// found = true;
// break;
// }
// return found
// }
public int search(TYPE element) {
return exponentialSearch(element);
}
private boolean binarySearchComparable(TYPE element) {
boolean found = false;
int lo = 0;
int hi = count - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (list[mid].compareTo(element) < 0) {
lo = mid + 1;
}
else if (list[mid].compareTo(element) > 0) {
hi = mid - 1;
}
else if (list[mid].compareTo(element) == 0) {
found = true;
break;
}
}
System.out.print("Single");
return found;
}
private int exponentialSearch(TYPE key){
int ind = binarySearchComparator(key);
// If element is not present
if (ind == -1)
return -1;
// Count elements on left side.
int count = 1;
int left = ind - 1;
int i = 1;
while (left >= 0 && (comparator.compare(list[left], key)) == 0)
{
// lol[i] = list[left];
System.out.println(left+"lefttest");
i++;
count++;
left--;
}
// Count elements
// on right side.
int right = ind + 1;
try{
while (right < list.length && (comparator.compare(list[right], key)) == 0)
{
System.out.println(right+"righttest");
// lol[i] = arr[right];
i++;
count++;
right++;
}
}catch(Exception e){
}
return count;
}
private int binarySearchComparator(TYPE key) {
int low = 0;
int high = count - 1;
while (low <= high) {
int mid = (low + high) / 2 ;
TYPE midVal = list[mid];
int cmp = comparator.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -1; // key not found.
}
//To String Method
@Override
public String toString() {
String result = "";
for (int i = 0; i < count; i++)
result += list[i] + "\n";
return result;
}
}
名称类
public class Name {
// Data Types
private String firstName;
private String lastName;
// Constructors
public Name() {
}
public Name(String firstName, String lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
// setter
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
// getter
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public String getFullName(){
return firstName + " " + lastName;
}
@Override
public String toString() {
return "Name{" + "firstName=" + firstName + ", lastName=" + lastName + '}';
}
}
学生类
public class Student implements Comparable<Student>{
// Data Types
private String studID;
private Name name;
private String gender;
private String icNo;
private String mobileNo;
private Course course;
private String group;
private String dOB;
// Constructors
public Student() {
}
public Student(String studID, Name name, String gender, String icNo, String mobileNo, Course course, String group, String dOB) {
this.studID = studID;
this.name = name;
this.gender = gender;
this.icNo = icNo;
this.mobileNo = mobileNo;
this.course = course;
this.group = group;
this.dOB = dOB;
}
public Student(Name name) {
this.name = name;
}
// setter
public void setStudID(String studID) {
this.studID = studID;
}
public void setName(Name name) {
this.name = name;
}
public void setGender(String gender) {
this.gender = gender;
}
public void setIcNo(String icNo) {
this.icNo = icNo;
}
public void setMobileNo(String mobileNo) {
this.mobileNo = mobileNo;
}
public void setCourse(Course course) {
this.course = course;
}
public void setGroup(String group) {
this.group = group;
}
public void setdOB(String dOB) {
this.dOB = dOB;
}
// getter
public String getStudID() {
return studID;
}
public Name getName() {
return name;
}
public String getGender() {
return gender;
}
public String getIcNo() {
return icNo;
}
public String getMobileNo() {
return mobileNo;
}
public Course getCourse() {
return course;
}
public String getGroup() {
return group;
}
public String getdOB() {
return dOB;
}
@Override
public String toString() {
return "Student{" + "name=" + name + ", gender=" + gender + ", icNo=" + icNo + ", mobileNo=" + mobileNo + ", course=" + course + ", group=" + group + ", dOB=" + dOB + '}';
}
@Override
public int compareTo(Student object) { // Sort according to name if name same then sort according to gender and so on.
int c = this.name.getFullName().compareTo(object.getName().getFullName());
if(c == 0)
c = this.gender.compareTo(object.getGender());
if(c == 0)
c = this.icNo.compareTo(object.getIcNo());
if(c == 0)
c = this.mobileNo.compareTo(object.getMobileNo());
if(c == 0)
c = this.group.compareTo(object.getGroup());
if(c == 0)
c = this.dOB.compareTo(object.getdOB());
return c;
}
public static Student[] sort(Student[] object,String category){
Student[] array;
if(category.equals("ID")){
for (int i=1; i < object.length; i++) {
for(int j = 0 ; j < object.length - i ; j++)
if( (object[j].getGender().compareTo(object[j+1].getGender())) > 0 ){
Student lol = object[j];
object[j] = object[j+1];
object[j+1] = lol;
}
}
}
array = object;
return array;
}
}
类(class)类别
public class Course {
// Data Types
private String courseCode;
private String courseName;
private double courseFee;
// Constructors
public Course() {
}
public Course(String courseCode, String courseName, double courseFee) {
this.courseCode = courseCode;
this.courseName = courseName;
this.courseFee = courseFee;
}
// setter
public void setCourseCode(String courseCode) {
this.courseCode = courseCode;
}
public void setCourseName(String courseName) {
this.courseName = courseName;
}
public void setCourseFee(double courseFee) {
this.courseFee = courseFee;
}
// getter
public String getCourseCode() {
return courseCode;
}
public String getCourseName() {
return courseName;
}
public double getCourseFee() {
return courseFee;
}
@Override
public String toString() {
return "CourseCode = " + courseCode + "Course Name = " + courseName + "Course Fee = " + courseFee;
}
}
最佳答案
您可以使用二分搜索通过查找列表中元素的最小和最大索引来查找有序数组/列表中元素出现的次数。
我编写了(盲目地，未经测试，因为我没有其余的代码)两个函数，可以分别找到列表中元素的最小和最大索引
private int getMinIdx(TYPE key, int low, int high) {
int lowVal = list[low];
if ((low == high) || (low == high-1)) {
if (comparator.compare(lowVal, key) == 0) {
return low;
} else {
return high;
}
}
int mid = (low + high) / 2;
int midVal = list[mid];
int cmp = comparator.compare(midVal, key);
if (cmp < 0) {
return getMinIdx(key, mid, high);
} else {
return getMinIdx(key, low, mid);
}
}
private int getMaxIdx(TYPE key, int low, int high) {
int highVal = list[high];
if ((low == high) || (low == high-1)) {
if (comparator.compare(highVal, key) == 0) {
return high;
} else {
return low;
}
}
int mid = (low + high) / 2;
int midVal = list[mid];
int cmp = comparator.compare(midVal, key);
if (cmp > 0) {
return getMaxIdx(key, low, mid);
} else {
return getMaxIdx(key, mid, high);
}
}
请注意，当且仅当元素位于列表中时它们才起作用。但由于您有一个函数已经回答了这个问题，因此您所要做的就是在调用这两个函数之前使用它。它们是基于二分搜索的，因此它们的运行时间都是 O(log n)。
对于我上面编写的代码，我不向您提供任何保证(尤其是 return 部分，它可能需要额外的检查)。
尽管如此，计算数字的方法是合法的并且基于二分搜索，所以我很确定您在理解原理并将其适应您的代码时不会有任何问题。
关于java - 二分查找多个相同项目并计算出现次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58899729/